Heaps

What are Heaps and Why Do We Need Them?

The tree is an incredibly flexible data structure. If we further restrict the number of children of any node to two (binary tree), the resulting implementation can be more powerful still, with special properties that can make them easier to manipulate. A binary search tree is a good example of this. However, in return for this flexibility, tree data structures often have one fatal flaw. They are mostly constructed using pointers (instead of arrays). This dramatically reduces speed of access. When we search for a particular value, we have to iterate through the pointers until we get to the node that we seek. How can we create a binary tree structure that can be implemented by an array? We can do this if we put some additional constraints on this new data structure, which we will call a binary heap. A binary heap is, in fact, a binary tree that is complete and follows the heap property. A complete tree is one in which all nodes have exactly two children except for the nodes at the lowest level of the three. This lowest level, furthermore, must be filled from left to right - with no gaps or missing nodes in between. If we add these restrictions to a binary tree, it becomes possible to implement our new heap data structure using arrays. This, in turn, greatly increases efficiency since random access is now possible instead of sequential access as was the case when the tree was implemented using pointers. Because the heap is an efficient flexible data structure, languages such as java typically use this data structure for allocating memory by the compiler for all objects in a program. Finally, heaps implement on additional important property - the heap property.
The heap property says that if A is a parent node of B, then the value of node A is ordered with respect to the value of node B. The same ordering is applied across the entire heap. There are two classifications of heaps, max heap and min heap. In a max heap the values of the parents are greater than or equal to the values of all their children. In a min heap, the values of the parents are less than or equal to the values of all their children. In this course, we will only be dealing with max heaps such as the one shown on the right. Note that in a max heap, the largest value in the heap is always stored in the root node. As a reminder, the height of a complete binary heap is log(n) where n is the number of nodes in the tree. This formula will be important to us in our study of heaps.

Heap Efficiencies

  1. Finding the max element: In a max heap, the largest element is always at the root, so it takes O(1) to locate the max element in a max heap.
  2. Inserting an element: O(log n) since it is a tree
  3. Deleting an element: O(log n) since it is a tree
  4. Search for an element: Searching takes O(n) time. But as a practical matter, if the current node in a max heap is less than the value we are seeking, we need not examine any of the children of the current node. So on average, we check only O(n/2) nodes.

How to Build and Maintain Heaps

The following videos describe how to create a heap, add and delete elements. The last video shows how to implement a heap in a computer program using arrays. While watching these videos, try to understand why the additional restrictions we have put on the binary tree to create the heap were necessary for the array implementation.


The Structure of a Heap and How to Add Items



How to Remove Items from a Heap



How to Implement a Heap as an Array