Heaps

• A heap is a binary tree whose left and right subtrees have values less than their parents. The root of a heap is guaranteed to hold the largest node in the tree.

• Both the left and the right branches of the tree have the same properties.

• Heaps are often implemented in an array rather than a linked list. When arrays are used, we are able to calculate the location of the left and the right subtrees. Conversely, we can calculate the address of it’s parent.

• The tree is complete or nearly complete. The key value of each node is greater than or equal to the key value in each of its descendents. This structure is also called max- heap.

Two basic maintenance operations are performed on a heap.

• Insert a heap
• Delete a heap
• Two basic algorithms are – Reheap Up and Reheap Down

Useful Link:   www.sorting-algorithms.com/heap-sort

A heap is a data structure used to implement an efficient priority queue. The idea is to make it efficient to extract the element with the highest priority ­ the next item in the queue to be processed.

We could use a sorted linked list, with O(1) operations to remove the highest priority node and O(N) to insert a node. Using a tree structure will involve both operations being O(log2N) which is faster.

HEAP SORT C PROGRAM

http://www.freecprograms.com/heapsort.htm

-----------------------------------