Chapter 6 Priority Queues (Heaps)

6.1 Model

A priority queue is a data structure that allows at least the following two operations: insert, which does the obvious thing; and deleteMin, which finds, returns, and removes the minimum element in the priority queue. The insert operation is the equivalent of enqueue, and deleteMin is the priority queue equivalent of the queue’s dequeue operation.

6.3 Binary Heap

Binary heap have two properties, namely, a structure property and a heap-order property. As with AVL trees, an operation on a heap can destroy one of the properties, so a heap operation must not terminate until all heap properties are in order.

6.3.1 Structure Property

A heap is a binary tree that is completely filled, with the possible exception of the bottom level, which is filled from left to right. Such a tree is known as a complete binary tree.

It is easy to show that a complete binary tree of height has between and nodes. This implies that the height of a complete binary tree is , which is clearly .

For any element in array position , the left child is in position , the right child is in the cell after the left child , and the parent is in position .

6.3.2 Heap-Order Property

Since we want to be able to find the minimum quickly, it makes sense that the smallest element should be at the root.

In a heap, for every node , the key in the parent of is smaller than (or equal to) the key in .

6.3.3 Basic Heap Operations

insert

This general strategy is known as a percolate up; the new element is percolated up the heap until the correct location is found.

The time to do the insertion could be as much as , if the element to be inserted is the new minimum and is percolated all the way to the root.

deleteMin

This general strategy is known as a percolate down. We use the same technique as in the insert routine to avoid the use of swaps in this routine.

The worst-case running time for this operation is . On average, the element that is placed at the root is percolated almost to the bottom of the heap (which is the level it came from), so the average running time is .

6.3.4 Other Heap Operations

decreaseKey

The operation lowers the value of the item at position by a positive amount . Since this might violate the heap order, it must be fixed by a percolate up.

increaseKey

The operation increases the value of the item at position by a positive amount . This is done with a percolate down.

delete

The operation removes the node at position from the heap. This is done by first performing and then performing .

buildHeap

The binary heap is sometimes constructed from an initial collection of items. This constructor takes as input items and places them into a heap. Obviously, this can be done with successive inserts. Since each insert will take average and worst-case time, the total running time of this algorithm would be average but worst-case.

Theorem 6.1.

For the perfect binary tree of height containing nodes, the sum of the heights of the nodes is .

Proof.

It is easy to see that this tree consists of node at height , nodes at height , nodes at height , and in general nodes at height . The sum of the heights of all the nodes is then

Multiplying by gives the equation

We subtract these two equations and obtain Equation.

A complete tree is not a perfect binary tree, but the result we have obtained is an upper bound on the sum of the heights of the nodes in a complete tree. Since a complete tree has between and nodes, this theorem implies that this sum is , where is the number of nodes.

Although the result we have obtained is sufficient to show that buildHeap is linear, the bound on the sum of the heights is not as strong as possible. For a complete tree with nodes, the bound we have obtained is roughly .

6.5 d-Heaps

A simple generalization is a d-heap, which is exactly like a binary heap except that all nodes have children.

Notice that a d-heap is much shallower than a binary heap, improving the running time of inserts to . However, for large d, the deleteMin operation is more expensive, because even though the tree is shallower, the minimum of children must be found, which takes comparisons using a standard algorithm. This raises the time for this operation to

6.6 Leftist Heaps

Like a binary heap, a leftist heap has both a structural property and an ordering property. A leftist heap is also a binary tree. The only difference between a leftist heap and a binary heap is that leftist heaps are not perfectly balanced but actually attempt to be very unbalanced.

6.6.1 Leftist Heap Property

We define the null path length, , of any node to be the length of the shortest path from to a node without two children. Thus, the npl of a node with zero or one child is , while .

The leftist heap property is that for every node in the heap, the null path length of the left child is at least as large as that of the right child.

Theorem 6.2.

A leftist tree with nodes on the right path must have at least nodes.

Proof.

If , there must be at least one tree node. Otherwise, suppose that the theorem is true for . Consider a leftist tree with nodes on the right path. Then the root has a right subtree with nodes on the right path, and a left subtree with at least nodes on the right path (otherwise it would not be leftist). Applying the inductive hypothesis to these subtrees yields a minimum of nodes in each subtree. This plus the root gives at least nodes in the tree.

From this theorem, it follows immediately that a leftist tree of nodes has a right path containing at most nodes.

6.6.2 Leftist Heap Operations

The fundamental operation on leftist heaps is merging. Notice that insertion is merely a special case of merging, since we may view an insertion as a merge of a one-node heap with a larger heap.

You should check that these heaps really are leftist. Notice that the smallest elements are at the roots. In addition to space for the data and left and right references, each node will have an entry that indicates the null path length.

As mentioned above, we can carry out insertions by making the item to be inserted a one-node heap and performing a merge. To perform a , we merely destroy the root, creating two heaps, which can then be merged.

private static class Node<AnyType> {
    AnyType element;
    Node<AnyType> left;
    Node<AnyType> right;
    int npl;
}

6.7 Skew Heaps

A skew heap is a self-adjusting version of a leftist heap that is incredibly simple to implement. The relationship of skew heaps to leftist heaps is analogous to the relation between splay trees and AVL trees. Skew heaps are binary trees with heap order, but there is no structural constraint on these trees. Unlike leftist heaps, no information is maintained about the null path length of any node. The right path of a skew heap can be arbitrarily long at any time, so the worst-case running time of all operations is .

As with leftist heaps, the fundamental operation on skew heaps is merging. The merge routine is once again recursive, and we perform the exact same operations as before, with one exception. The difference is that for leftist heaps, we check to see whether the left and right children satisfy the leftist heap structure property and swap them if they do not. For skew heaps, the swap is unconditional; we always do it, with the one exception that the largest of all the nodes on the right paths does not have its children swapped.

6.8 Binomial Queues

6.8.1 Binomial Queue Structure

Binomial queues differ from all the priority queue implementations that we have seen in that a binomial queue is not a heap-ordered tree but rather a collection of heap-ordered trees, known as a forest. Each of the heap-ordered trees is of a constrained form known as a binomial tree. There is at most one binomial tree of every height. A binomial tree of height is a one-node tree; a binomial tree, , of height is formed by attaching a binomial tree, , to the root of another binomial tree, .

Binomial trees of height have exactly nodes, and the number of nodes at depth is the binomial coefficient . If we impose heap order on the binomial trees and allow at most one binomial tree of any height, we can represent a priority queue of any size by a collection of binomial trees.

6.8.2 Binomial Queue Operations

Merging

Insertion

Deletion

6.8.3 Implementation of Binomial Queues

public class BinomialQueue<AnyType extends Comparable<? super AnyType>> {
    private static class Node<AnyType> {
        AnyType element;
        Node<AnyType> leftChild;
        Node<AnyType> nextSibling; 
    }
    
    private Node<AnyType>[] theTrees;
    private int currentSize;
}