.NET 1.1+Binary Heaps
A binary heap is a data structure, based upon a complete binary tree, that allows the first item in an ordered set to be quickly extracted. Heaps are used in several popular algorithms, including the heapsort method for ordering elements in a collection.
What is a Binary Heap?
In this article I will describe the structure of a binary heap and the processes used to build a heap, add data to it and remove the top item. We'll then create the code for a heap and its operations using C#.
A binary heap is a data structure that is used in a number of commonly seen algorithms and data structures. These include the heapsort algorithm, seen later in this article, and the priority queue data structure. Heaps are based upon binary trees with two constraints. These are that the binary tree must be complete and that nodes must be correctly ordered with respect to their parents.
Complete Tree Constraint
Let's look at the complete constraint first. When constructing a binary tree, we start with a root node, which may have zero, one or two children. Each child node may also be a parent of zero, one or two children. These nodes can also have up to two children and this can continue for any number of levels.
The following image shows a representation of a valid binary tree. The root node has two children. The child on the left also has two children and the child on the right has just one. The three nodes at the lowest level are called leaf nodes, because they have no children.
If all of the leaf nodes of a binary tree are at the same level and all non-leaf nodes have two children, the tree in known as a perfect tree. This is not a requirement for a heap. The following diagram represents a perfect tree.
The constraint for a heap is that the tree must be complete. This means that every level of the tree except for the lowest level is completely filled. The final level of the tree need not be filled. However, the nodes in the lowest level must be as far to the left of the tree as possible.
The first binary tree image is not complete because of the gap between the second and third nodes. The tree in the diagram below is complete because there are no gaps to the left of any leaf nodes and all of the levels except the last are completely full.
Ordering Constraint
Although the image above is a complete binary tree, it does not qualify as a heap because it fails on the ordering constraint. Heaps are used for sorting operations and the first item when the contents of the heap are sorted will always be the root node. Every child node must also be ordered with respect to its parent. For example, if the heap is used to sort numbers into ascending order, the root node will be the lowest value and every child will have an equal or higher value when compared with its parent. The tree above does not meet this condition because the 2 appears beneath the 9.
The image below shows a valid heap because the parent to child ordering is correct and the binary tree is complete. This image represents a min heap. This is a heap that is organised so that the minimum value appears at the root. The opposite is a max heap, where the maximum value is held in the root node and each child has an equal or lower value than its parent.
3 February 2013