Tuesday, September 26, 2006

Heaps

Topics

• Heap properties:
•     Each node is greater or equal to all its children
•     The tree is perfectly balanced, with missing nodes only to the right on the bottom row.
• Heaps do not necessarily maintain a searchable order, but they do form natural priority queues
• Insertion is done by placing the new node at the first available position from the left on the bottom row, and then swapping up until the heap property is restored.
• Inserting into a tree is O(lg n).
• Removal is from the root, and then swapping the last node from the left on the bottom row to the root, and then swapping down until the heap property is restored.
• Removal of the highest node is also O(lg n).
• Searching, however is O(n).
• Heaps are almost always implemented as arrays instead of with nodes and pointers.  Since the heap is always perfectly balanced, array implementation is very efficient.  
• A node implementation of a heap would have to maintain parent pointers to be efficient

Readings

Chapter 6, Section 6.9.