Priority Queues

CS240E: Data Structures and Data Management (Enriched)

2019 Winter, David Duan

Priority QueuesCS240E: Data Structures and Data Management (Enriched)2019 Winter, David DuanAbstract Data TypesADTStack ADTQueue ADTPriority QueueUsing a Priority Queue to SortRealizations of Priority QueuesUnsorted Arrays / Unsorted Linked ListsSorted Arrays / Sorted Linked ListsHeapsRepresentationOperations on HeapsInsertionDelete MaxPriority Queue Realization Using HeapsSorting using HeapsHeapSortBuilding Heaps by Bubble-upBuilding Heaps by Bubble-downHeapSort ImplementationOther Heap OperationsGetMaxChangePriorityDeleteHeap Merge/JoinWorst-Case Heap JoiningExpected MergePseudocodeGraphical IllustrationExpected Runtime AnalysisBinomial HeapBinomial TreeBinomial Heap Binomial Heap OperationsAmortized Analysis (via Potential Function)Improvement on Worst-Case PerformanceMagic Trick

Abstract Data Types

Stack ADT
Queue ADT

Priority Queue

Using a Priority Queue to Sort
Realizations of Priority Queues
Unsorted Arrays / Unsorted Linked Lists
Sorted Arrays / Sorted Linked Lists


A heap is a tree-based data structure satisfying two properties:

  1. The tree is complete: all the levels of heap are completely filled, except (possibly) for the last level; the filled items in the level are left-justified.
  2. The tree satisfies the heap property: for any node , the key of its parent is larger than or equal to the key of (in a max-heap).


  1. In a heap, the highest (or lowest) priority element is always stored at the root.
  2. A heap is not a softed structure; it can be regarded as being partially sorted.
  3. A binary heap with nodes has height .

We usually do not store heaps as binary trees but structured arrays.

We should hide implementation details using helper functions such as root(), parent(i), last(n), hasLeftChild(i), etc.

Operations on Heaps

Place the new key at the first free leaf, then perform a fix-up:

The new item bubbles up until it reaches its correct place in the heap. Insertion has runtime .

Delete Max

We replace root, which is the max item of the heap, by the last leaf and remove last leaf, then perform a fix-down:

The new root bubbles down until it reaches its correct place in the heap. DeleteMax has runtime .

Priority Queue Realization Using Heaps

We can store items in a PQ in array and keep track of its size:

Sorting using Heaps

Recall that any PQ can be used to sort in time . Using the binary-heaps implementation of PQs, we obtain:

Since both operations run in for heaps, PQ-Sort using heaps takes time.

We can improve this with two simple tricks:

  1. Heaps can be built faster if we know all input in advance.
  2. We can use the same array for input and heap, so additional space. This is called Heapsort.
Building Heaps by Bubble-up

Problem: Given times in , build a heap containing all of them.

Solution 1: Start with an empty heap and inserting item one at a time. This corresponds to doing fix-ups, so worst-case .

Building Heaps by Bubble-down

Problem: Given times in , build a heap containing all of them.

Solution 2: Using fix-downs instead:

A careful analysis yields a worst-case complexity of , which means a heap can be built in linear time.

HeapSort Implementation

Idea: PQ-Sort with heaps

Improvement: use same input array for storing heap.

The for-loop takes time and the while-loop takes time.

Other Heap Operations

Heap Merge/Join

Problem join(H1, H2): create a heap that stores items of both and .

Solution We present three ideas:

  1. An algorithm works for tree-based implementation using worst case time.

    1. Remark. This algorithm can be improved to .
  2. A randomized algorithm (destroys structural property of heaps) where .

  3. An algorithm using higher-degree heaps with amortized runtime .

Worst-Case Heap Joining

Given , , , , we want to create a heap combining both heaps.

Case I. Both heaps are full and they have the same height:

  1. Create a new heap and set the root 's priority to .
  2. Set to be 's left child and to be 's right child.
  3. Call deleteMax(). Since deleteMax() also takes care of structural property, we are done.

The runtime is dominated by deleteMax() which has time.

Case II. Both heaps are full and has a smaller height:

Phase I: Merge

  1. Let represent 's height. Since , we can find a subheap of with the same height as . In the left diagram, subheaps , , , and are such heaps.

  2. Since , we use Case I's strategy to merge into :

    1. Create a new heap and set the root 's priority to .
    2. Set and to be 's left and right child, respectively.
    3. Replace with this new heap.

    We arrive at the right diagram.

Phase II: Adjust

To get rid of node, consider the following three nodes:

  1. Node : root of subheap .
  2. Node : root of subheap .
  3. Node : 's parent, which originally was 's parent.

We have the following observations:

  1. and are valid heaps by construction, hence both satisfy the heap property.

  2. By heap ordering property of , was 's parent previously implies , so subheap (and its root ) will not violate the heap property.

  3. The only problem is we don't know about the relationship between and .

    • If , then we can bubble up and call deleteMax().
    • If however, the heap ordering property is broken. Moreover, if , then there might exist more elements in that has a larger value than , or more ancestors of is less than .

To fix the problem (when ):

  1. For all ancestors of , call fix-down(a).

    1. This guarantees all ancestors of will be bubbled into the correct place.
    2. In the worst case, there are such ancestors (), and each fix-down(a) requires comparisons (again, ), so overall this step takes .
  2. Call deleteMax(): After those fix-down's, will be at the root position. Calling deleteMax() effectively removes .

Overall, the runtime is dominated by those fix-down's and hence has runtime .

Case III. is full but is not.

This takes time. We omit this case.

Case IV. Both are not full.

  1. We split into heaps that are full.

    • In the above diagram, elements labeled with same letter are grouped into one full heap, e.g., the entire right subheap (labeled k) is a full heap, and the node F itself is a heap (because we have nothing to group it with).
    • Since the heap is not full, there will always be a path from root to leaf, where each node on the path is a one-node heap. In the diagram above, this path is represented by A -> B -> D -> E -> F.
    • Since the path has at least one-node heaps, overall we get full heaps.
  2. For each full subheap, merge them into using Case III. Since each merge takes and we have full heaps, we end up with time.

Conclusion Overall, the runtime is dominated by Case IV: time.

Expected Merge
Graphical Illustration

Suppose we want to merge the following two heaps.

We see that root of left heap is greater than root of right heap (see line 7).

We randomly pick a child of and ended up with (see line 8).

We see (see line 3).

We randomly pick a child of and ended up with (see line 4).

We keep doing this:

Finally, we see that r1 is NIL and move (subheap with root ).

Return from call stack:

Return from call stack & compare with : we move the subheap with root .

Return from call stack & compare with : we move the subheap with root .

We are done!

Expected Runtime Analysis

Recall the expected runtime of a randomized algorithm can be expressed as:

We want to design the randomization such that all instances of size have equally good performance because the expected runtime depends on the of every instance.

Before we analyze the expected runtime of heap merge, let us first consider a simpler problem:

Problem Given a binary tree, you do a random walk downtime until you reach NIL. What is the runtime for this? We make no assumption on the tree, i.e., it may be very unbalanced.

Lemma The expected runtime (i.e., on a tree of nodes) is .

Proof. Assume that the time to go from a node to a randomly chosen child is at most . We claim that . We prove by induction.

Back to the heap merge analysis, we can view it as going down in both heaps randomly until one hits a NIL child. Then

Binomial Heap

Recall that merge is easy for list ( for concatenation). To achieve our goal of worst-case merging, we can store a list of trees that satisfy the heap-property.

Binomial Tree

A binomial tree is defined recursively as follows:

  1. A binomial tree of order is a single node.
  2. A binomial tree of order has a root node whose children are roots of binomial trees of order (in this order).

Because of its unique structure, a binomial tree of order can be constructed from two trees of order trivially by attaching one of them as the left-most child of the root of the other tree. This feature is central to the merge operation of a binomial heap, which is its major advantage over the conventional heaps.

Remark. The name comes from the shape: a binomial tree of order has nodes at depth .

Claim. A binomial tree of order has nodes with height .

Proof. We prove by induction. The base case is trivial. Suppose this is true for . Then binomial tree contains two copies of , so has nodes. Because the max depth of a node in is one greater than the max depth in , by the inductive hypothesis, the maximum depth is .

Binomial Heap

A binomial heap is implemented as a set (or list, as presented in our class) of binomial trees that satisfy the binomial heap properties:

  1. Each binomial tree in a heap obeys the heap ordering property.
  2. There can only be either one or zero binomial trees for each order, include zero order.

The first property ensures that the root of each binomial tree contains the maximum in the tree, which applies to the entire heap.

The second property implies that a binomial heap with nodes consists of at most binomial trees. In fact, the number of orders of these trees are uniquely determined by the number of nodes : each binomial tree corresponds to the bits in the binary representation of number . For example, if a heap contains nodes, then this binomial heap with nodes will consist of three binomial trees of order , and .

Binomial Heap Operations

Let be the list of trees and be the degree at the root of tree (take the max).

Merge: as we are basically concatenating lists.

Insert: for the same reason. In fact, insertion can be seen as merging as well.

DeleteMax: ).

  1. Locate the max: search among all roots, of them so for searching.

  2. Remove the max and merge the subtrees into the heap: suppose the tree has children, then we need to perform insertions. Hence time for merging.

  3. Cleanup: we want to merge trees together so after this step, no two trees have the same degrees in the list.

Amortized Analysis (via Potential Function)

Lemma. If all trees were built with these operations, .

Proof. . This also implies .

Define , where is the number of trees at time stamp and is a constant bigger than all constants in all other terms. Recall the amortized runtime of step is defined to be .

To show merge(R1, R2) has amortized time :

Time to analyze deleteMax():

Improvement on Worst-Case Performance

So far we have achieved amortized runtime for deleteMax(). If we are willing to trade runtime for merge/insert for deleteMax(), we can achieve worst-case for all three operations.

By calling clean-up after every operation (insert/merge), we can keep . Recall clean-up takes . Enforcing this would make insert/merge/deleteMax all achieve worst-case runtime.

Magic Trick

We can use a binary tree to store a tree with an arbitrary degree!

The new binary tree has the same nodes as . For node in , its left child in is the left-most child in and right child in is its sibling in .

Source: A very very interesting paper to read.