min heap heapify code example

Example 1: python code for heap using heapify

#Implementing Heap Using Heapify Method in Python 3
#MaxHeapify,MinHeapify,Ascending_Heapsort,Descending_Heapsort
class heap:
    
    def maxheapify(self,array):
        n=len(array)
        for i in range(n//2-1,-1,-1):
            self._maxheapify(array,n,i)
            
            
    def _maxheapify(self,array,n,i):
        l=2*i+1
        r=2*i+2
        if l<n and array[l]>array[i]:
            largest=l
        else:
            largest=i
        if r<n and array[r]>array[largest]:
            largest=r
        if (largest!=i):
            array[largest],array[i]=array[i],array[largest]
            self._maxheapify(array,n,largest)
            
            
    def minheapify(self,array):
        n = len(array)
        for i in range(n//2-1,-1,-1):
            self._minheapify(array,n,i)
            
            
    def _minheapify(self,array,n,i):
        l=2*i+1
        r=2*i+2
        if l<n and array[l]<array[i]:
            smallest = l
        else:
            smallest = i
        if r < n and array[r]<array[smallest]:
            smallest = r
        if (smallest != i):
            array[smallest], array[i] = array[i], array[smallest]
            self._minheapify(array, n, smallest)
            
            
    def descending_heapsort(self,array):
        n = len(array)
        for i in range(n // 2 - 1, -1, -1):
            self._minheapify(array, n, i)
        for i in range(n - 1, 0, -1):
            array[0], array[i] = array[i], array[0]
            self._minheapify(array, i, 0)


    def ascending_heapsort(self,array):
        n=len(array)
        for i in range(n//2-1,-1,-1):
            self._maxheapify(array,n,i)
        for i in range(n-1,0,-1):
            array[0],array[i]=array[i],array[0]
            self._maxheapify(array,i,0)

b=[550,4520,3,2340,12]
a=heap()

a.maxheapify(b)
print('Max Heapify -->',b)

a.minheapify(b)
print('Min Heapify -->',b)

a.ascending_heapsort(b)
print('Ascending Heap Sort -->',b)

a.descending_heapsort(b)
print('Descending Heap Sort -->',b)

Example 2: heap sort heapify and max heap in binary tree

Implementation of heap sort in C:

#include <stdio.h>
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]<heap[c] && c<j)    /* again rearrange to max heap array */
           {
               temporary = heap[root];
               heap[root] = heap[c];
               heap[c] = temporary;
           }
           root = c;
       } while (c < j);
   }
   printf("\n The sorted array is : ");
   for (i = 0; i < array_size; i++)
      printf("\t %d", heap[i]);
}

Tags:

Cpp Example