Notes on Heap

Heap is essentially have to types of operation:

Insertion and deletion.

Insertion: ( it can also initial the heap), to keep  is a a complete tree, insert from the last position. This would also help if the heap is built in an array, so you can insert from the last element. 

Deletion ( also, to get the most "significant" element from the heap), delete the top one, then do heapfy again, this is equivalent to delete the first element from the array, then go through the array, do the comparison, to find which one should be put into the 1st place to fulfill the empty. 

Max-Heapify^[4](A, i):
 left ← 2i
 right ← 2i + 1
 largest ← i
 if left ≤ heap-length[A] and A[left] > A[i] then:
 largest ← left
 if right ≤ heap-length[A] and A[right] > A[largest] then:
 largest ← right
 if largest ≠ i then:
 swap A[i] ↔ A[largest]
 Max-Heapify(A, largest)

Binary heap - Wikipedia, the free encyclopedia

http://en.wikipedia.org/wiki/Binary_heap

Heap is often used for priority queue.

Priority queue - Wikipedia, the free encyclopedia

http://en.wikipedia.org/wiki/Priority_queue

--

♥ ¸¸.•*¨*•♫♪♪♫•*¨*•.¸¸♥