Heap and Heapsort

Heap/Heapsort is not difficult to understand when you reading online articles/watching online videos, but without using it everyday, it is quite easy to forget the evil details.

Here are some notes to help memorizing this.

(1) Min/Max heap, is a  a Complete Binary Tree with its parent nodes smaller or greater than its two children.

a A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.

normally we use array to represent the heap.

at index i, its children nodes will be: 2*i + 1, 2*i+2;

As we can see the Min/Max heap is a kind of partially sorted structure already.

(2) how to build a heap, normally it is O(n) time

it starts from bottom , looking at the code it is easier to understand then words.

MinHeap::MinHeap(int a[], int size)
{
    heap_size = size;
    harr = a; // store address of array
    int i = (heap_size - 1)/2;  // start from the bottom heap! O(n)
    while (i >= 0)
    {
       MinHeapify(i);  // heapify do every upper parent nodes
       i--;
    }
}

void MinHeap::MinHeapify(int i)
{
   int l = 2*i+1;
   int r = 2*i + 2;
   int smallest = i;
   if (l <= heap_size && harr[l] <= harr[i])
       smallest = l;
   if (r <= heap_size && harr[r] <= harr[smallest])
       smallest = r;
   if (smallest != i)
   {
      swap(&harr[i], &harr[smallest]);
     // magic thing here, since we swapped,  smallest-node may not a valid heap structure anymore,
     //so we need to check and adjust it from up to down
     MinHeapify(smallest);
   }
}

(3) Heap sort/Priority Queue
Most heavy-lifting job are done in (2), so doing the sorting it quite easy, just peek from top, we got Max/Min,

or we  exchange top with bottom node ( swap array[0] with array[size-1], then do the heaplify( array), we will get new min/max)

(4) more applications

the heap structure/algorithym is quite useful, some meanfully applications are:

sort nearly sorted ( K sorted array)

K largest/smallest element in an array

 

References:

http://www.geeksforgeeks.org/heap-sort/

Please rate this


Leave a Reply

Your email address will not be published. Required fields are marked *


*

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>