Module 2: Priority Queues¶

Abstract Data Types¶

Abstract Data Type (ADT)

A description of information and a collection of operations on that information.

The information is accessed only through the operations.

ADT Stack

An ADT consisting of a collection of items with operations:

push: Add an item to the stack.
pop: Remove and return the most recently added item.

Items are removed in LIFO (last-in first-out) order.

We can have extra operations: size, is-empty, and top

ADT Stack can easily be realized using arrays or linked lists such that operations taking constant time.

Queue

An ADT consisting of a collection of items with operations:

enqueue (or append or add-back): Add an item to the queue.
dequeue (or remove-front): Remove and return the least recently inserted item.

Items are removed in FIFO (first-in first-out) order.

We can have extra operations: size, is-empty, and peek/front

ADT Queue can easily be realized using (circular) arrays or linked lists such that operations taking constant time.

ADT Priority Queue¶

ADT Priority Queue

Priority Queue generalizes both ADT Stack and ADT Queue.

It is a collection of items (each having a priority or key) with operations

insert: inserting an item tagged with a priority
delete-max: removing and returning an item of highest priority.

We can have extra operations: size, is-empty, and get-max

This is a maximum-oriented priority queue. A minimum-oriented priority queue replaces operation delete-max by delete-min.

**PQ-Sort(A[0...n − 1])**
initialize PQ to an empty priority queue

for i←0 to n−1 do
    PQ.insert(an item with priority A[i])
for i←n−1 downto 0 do
    A[i] ← priority of PQ.delete-max()

Any priority queue can be used to sort in time: \(O\)(initialization + \(n\) · insert + \(n\) · delete-max)

Binary Heaps¶

A (binary) heap is a certain type of binary tree.

A binary tree is either

empty, or
consists of three parts: a node and two binary trees (left subtree and right subtree).

Terminology: root, leaf, parent, child, level, sibling, ancestor, descendant, etc.

Level \(l\) = all nodes with distance \(l\) from the root. Root is on level \(0\).

Height \(h\) = maximum number for which level \(h\) contains nodes. Single-node tree has height \(0\), empty tree has height \(−1\).

Any binary tree with height \(h\) has \(n \leq 2^{h+1}-1\) nodes. So height \(h \geq \log(n+1)-1 \in \Omega(\log n)\).

Heap

A heap ****is a binary tree with the following two properties:

Structural Property: All the levels of a heap are completely filled, except (possibly) for the last level. The filled items in the last level are left-justified.
Heap-order Property: For any node \(i\), the key of the parent of \(i\) is larger than or equal to key of \(i\).

The full name for this is max-oriented binary heap. (For a min-heap, the key of any parent node is less than or equal to the key of its children.)

Lemma

The height of a heap with \(n\) nodes is \(\Theta(\log n)\).

Storing heaps in arrays:

Heaps should not be stored as binary trees! Let \(H\) be a heap of \(n\) items and let \(A\) be an array of size \(n\). Store root in \(A[0]\) and continue with elements level-by-level from top to bottom, in each level left-to-right.

It is easy to navigate the heap using this array representation:

the root node is at index \(0\) (We use “node” and “index” interchangeably in this implementation.)
the last node is \(n − 1\) (where \(n\) is the size)
the left child of node \(i\) (if it exists) is node \(2i + 1\)
the right child of node \(i\) (if it exists) is node \(2i + 2\)
the parent of node \(i\) (if it exists) is node \(\lfloor \frac{i-1}{2} \rfloor\)
these nodes exist if the index falls in the range \(\{0, . . . , n−1\}\)

Binary Heaps as PQ realization¶

Insert in Heaps:

Place the new key at the first free leaf
Use fix-up to restore heap-order.

**insert(x)**

l ← last()+1
A[l] ← x // assume dynamic array used
increase size // size: stored by PQ
fix-up(A, l)

**fix-up(A, i)**
i: an index corresponding to a node of the heap

while parent(i) exists and A[parent(i)].key < A[i].key do
    swap A[i] and A[parent(i)]
    i ← parent(i)

Time: \(O(\text{height of heap}) = O(\log n)\) (and this is tight)

delete-max in Heaps

The maximum item of a heap is just the root node.
We replace root by the last leaf (last leaf is taken out).
The heap-order property might be violated: perform a fix-down:

**fix-down(A, i)**
A: an array that stores a heap of size n
i: an index corresponding to a node of the heap

while i is not a leaf do
    j ← left child of i // Find the child with the larger key
    if (i has right child and A[right child of i].key > A[j].key)
        j ← right child of i
    if A[i].key ≥ A[j].key break
    swap A[j] and A[i]
    i ← j

Time: \(O(\text{height of heap}) = O(\log n)\) (this is tight)

**delete-max()**

l ← last()
swap A[root()] and A[l]
decrease size
fix-down(A, root(), size)
return A[l]

Time: \(O(\text{height of heap}) = O(\log n)\) (and this is tight)

Binary heap are a realization of priority queues where the operations insert and delete-max take \(\Theta(\log n)\) time.

PQ-sort and heap-sort¶

Sorting using heaps¶

Using the binary-heaps implementation of PQs, we obtain:

**PQ-sort-with-heaps(A)**
initialize H to an empty heap

for i←0 to n−1 do
    H.insert(A[i])
for i←n−1 downto 0 do
    A[i] ← H.delete-max()

both operations run in \(O(\log n)\) time for heaps; PQ-sort using heaps takes \(O(n \log n)\) time (and this is tight).

Building Heaps with `fix-up`¶

Solution 1:

**simple-heap-building(A)**
A: an array

initialize H as an empty heap
for i ← 0 to A.size() − 1 do
    H.insert(A[i])

This corresponds to doing fix-ups.
Worst case running time: \(O(n\log n)\) (this is tight)

Building Heaps with `fix-down`¶

Solution 2:

**heapify(A)**
A: an array

n ← A.size()
for i ← parent(last()) downto root() do
    fix-down(A, i , n)

A careful analysis yields a worst-case complexity of \(\Theta(n)\).
A heap can be built in linear time.

Efficient sorting with heaps¶

Idea: PQ-sort with heaps.

\(\mathbf{O(1)}\) auxiliary space: Use same input-array \(A\) for storing heap.

**heap-sort(A)**

// heapify
n ← A.size()
for i ← parent(last()) downto 0 do
    fix-down(A, i , n)
// repeatedly find maximum
while n>1
    // ‘delete’ maximum by moving to end and decreasing n
    // note we decrease n here not decrease size
    swap items at A[root()] and A[last()]
    decrease n
    fix-down(A, root(), n)

The for loop takes \(\Theta(n)\) time and the while-loop takes \(\Theta(n\log n)\) time.

Heap Summary¶

Binary heap:

A binary tree that satisfies structural property and heap-order property.

Heaps are one possible realization of ADT Priority Queue:

insert takes time \(O(\log n)\)
delete-max takes time \(O(\log n)\)
Also supports findMax in time \(O(1)\) (This is the root of \(A\))

A binary heap can be built in linear time (via heapify)

PQ-sort with binary heaps leads to a sorting algorithm with \(O(n \log n)\) worst-case run-time (heap-sort)

We have seen here the max-oriented version of heaps (the maximum priority is at the root).

There exists a symmetric min-oriented version that supports insert and delete-min with the same run-times.