Heap Properties

Now that you know what a heap is, let’s examine some of its interesting properties.

While the heap condition dictates that the heap be ordered a certain way, this ordering is still useless when it comes to searching for a value within the heap.

For example, let’s say that in the above heap, we want to search for the value 3. If we start at the root node of 100, should we search among its left or right descendants? In a binary search tree, we’d know that the 3 must be among the 100’s left descendants. In a heap, however, all we know is that the 3 has to be a descendant of the 100, and can’t be its ancestor. But we’d have no idea as to which child node to search next. Indeed, the 3 happens to be among the 100’s right descendants, but it could have also easily been among its left descendants.

Because of this, heaps are said to be weakly ordered as compared to binary search trees. While heaps have some order, as descendants cannot be greater than their ancestors, this isn’t enough order to make heaps worth searching through.

Another property of heaps, that may be obvious by now but is worth calling attention to, is in a heap, the root node will always have the greatest value. (In a min-heap, the root will contain the smallest value.) This will be the key as to why the heap is a great tool for implementing priority queues. In the priority queue, we always want to access the value with the greatest priority. With a heap, we always know that we can find this in the root node. Thus, the root node will represent the item with the highest priority.

The heap has two primary operations: inserting and deleting. As we noted, searching within a heap would require us to inspect each node, so search isn’t an operation usually implemented in the context of heaps. (A heap can also have an optional read operation, which would simply look at the value of the root node.)

Before we move on to how the heap’s primary operations work, let me define one more term, since it’ll be used heavily in the upcoming algorithms.

The heap has something called a last node. A heap’s last node is the rightmost node in its bottom level.

Take a look at the .

In this heap, the 3 is the last node, since it’s the rightmost node in the bottom row.

Next, let’s get into the heap’s primary operations.