Example 1: max heap c++
#include
using namespace std;
void max_heap(int *a, int m, int n) {
int j, t;
t = a[m];
j = 2 * m;
while (j <= n) {
if (j < n && a[j+1] > a[j])
j = j + 1;
if (t > a[j])
break;
else if (t <= a[j]) {
a[j / 2] = a[j];
j = 2 * j;
}
}
a[j/2] = t;
return;
}
void build_maxheap(int *a,int n) {
int k;
for(k = n/2; k >= 1; k--) {
max_heap(a,k,n);
}
}
int main() {
int n, i;
cout<<"enter no of elements of array\n";
cin>>n;
int a[30];
for (i = 1; i <= n; i++) {
cout<<"enter elements"<<" "<<(i)<>a[i];
}
build_maxheap(a,n);
cout<<"Max Heap\n";
for (i = 1; i <= n; i++) {
cout<
Example 2: heap sort
// @see https://www.youtube.com/watch?v=H5kAcmGOn4Q
function heapify(list, size, index) {
let largest = index;
let left = index * 2 + 1;
let right = left + 1;
if (left < size && list[left] > list[largest]) {
largest = left;
}
if (right < size && list[right] > list[largest]) {
largest = right;
}
if (largest !== index) {
[list[index], list[largest]] = [list[largest], list[index]];
heapify(list, size, largest);
}
return list;
}
function heapsort(list) {
const size = list.length;
let index = ~~(size / 2 - 1);
let last = size - 1;
while (index >= 0) {
heapify(list, size, --index);
}
while (last >= 0) {
[list[0], list[last]] = [list[last], list[0]];
heapify(list, --last, 0);
}
return list;
}
heapsort([4, 7, 2, 6, 4, 1, 8, 3]);
Example 3: heap sort heapify and max heap in binary tree
Implementation of heap sort in C:
#include
int main()
{
int heap[10], array_size, i, j, c, root, temporary;
printf("\n Enter size of array to be sorted :");
scanf("%d", &array_size);
printf("\n Enter the elements of array : ");
for (i = 0; i < array_size; i++)
scanf("%d", &heap[i]);
for (i = 1; i < array_size; i++)
{
c = i;
do
{
root = (c - 1) / 2;
if (heap[root] < heap[c]) /* to create MAX heap array */
{ // if child is greater than parent swap them
temporary = heap[root]; // as structure is of complete binary tree
heap[root] = heap[c]; // it took logn steps to reach from root to leaf
heap[c] = temporary;
}
c = root;
} while (c != 0);
}
printf("Heap array : ");
for (i = 0; i < array_size; i++)
printf("%d\t ", heap[i]); //printing the heap array
for (j = array_size - 1; j >= 0; j--)
{
temporary = heap[0];
heap[0] = heap[j] ; /* swap max element with rightmost leaf element */
heap[j] = temporary;
root = 0;
do
{
c = 2 * root + 1; /* left node of root element */
if ((heap[c] < heap[c + 1]) && c < j-1)
c++;
if (heap[root]