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/
