Week 7. Priority Queues and Heaps

Priority Queues

Priority Queue

A priority queue is a collection of elements, called values, each having an associated key that is provided at the time the element is inserted.

A key-value pair inserted into a priority queue is called an entry. Keys are parameters or properties according to which we can compare the objects; keys are assigned for each object in a collection, for example we can compare companies by earnings or by number of employees.

Formally: a key is an object that is assigned to an element as a specific attribute for that element, which can be used to identify or weight that element.

Link to original

Total Order Relation

Total Order Relations $\le$ are relations with the properties: reflexive, anti-symmetric and transitive. A comparison rule that satisfies these three properties will never lead to a comparison contradiction.

Link to original

Priority Queue ADT

Priority Queue (ADT)

Methods in an ADT:

• insert(k,x): inserts an entry with key $k$ and value $x$ into a priority key $P$.
• removeMin(): removes the entry with smallest key from $P$.
• min(): returns but does not remove an entry of $P$ with smallest key.
• size(): returns the number of entries in priority queue $P$.
• isEmpty(): tests whether priority queue $P$ is empty.

Entry ADT

An entry in a priority key is simply a key-value pair. There may be two methods: getKey(), getValue().

Comparator ADT

A comparator encapsulates the action of comparing two objects according to a given Total Order Relation.

The primary method of the comparator is:

• compare(x,y): returns an integer $i$ such that:
  • $i<0$ if $x<y$
  • $i=0$ if $x=y$
  • $i>0$ if $x>y$

Link to original

Implementation with List

We may implement a sequence-based priority queue in one of two ways:

Unsorted List	Sorted List
insert takes $O(1)$ time since we can insert the item at the beginning or end of the sequence	insert takes $O(n)$ time since we have to find the place where to insert the time
removeMin and min take $O(n)$ time since we have to traverse the entire sequence to find the smallest key	removeMin and min take $O(1)$ time since the smallest key is at the beginning

In both cases, size and isEmpty take $O(1)$.

Priority Queue Sorting We can use a priority queue to sort a set of comparable elements.

1. Put the elements into the queue using insert.
2. Remove the elements in sorted order with a series of removeMin ops.

Running time depends on the implementation.

Selection Sort

Selection sort is the variation of priority queue sort where the priority queue is implemented with an unsorted sequence. The running time is as follows:

1. insert items with $n$ operations takes $O(n)$ time.
2. removing $n$ elements with removeMin takes $O(n^2)$ time.

Hence, selection sort runs in $O(n^2)$ time.

Insertion Sort

Insertion sort is the variation of priority queue sort where the priority queue is implemented with a sorted sequence. The running time is as follows:

1. insert items with $n$ operations takes $O(n^2)$.
2. removing $n$ elements with removeMin takes $O(n)$ time.

Hence, insertion sort runs in $O(n^2)$ time.

Heaps

Heap (Data Structure)

A heap is a binary tree storing keys at its nodes and satisfying the following properties:

• Order (heap)

  Heap-Order: for every internal node $v$ other than the root, $key(v)\ge key(parent(v))$.

  Link to original

• Complete Binary Tree: let $h$ be the height of the heap For $i=0,\dots ,h-1$, there are $2^i$ nodes of depth $i$. At depth $(h-1)$, the internal nodes are to the left of the external nodes.
• The last node of a heap is the rightmost node of maximum depth.

Height (heap)

Height of a Heap A heap storing $n$ keys has height $O(\log n)$. Proof by applying the complete binary tree property:

• Let $h$ be the height of a heap storing $n$ keys.
• Since there are $2^i$ keys at depth $i=0,\dots ,h-1$ and at least one key at depth $h$, we have $n\ge 1+2+4+\dots +2^{h-1}+1$.
• Hence, $n\ge 2^h$ or otherwise $h\le \log n$.

Link to original

Link to original

Priority Queue Implementation with Heap

We can use a heap to implement a priority key, we store one (key, value) item at one node. We keep track of the position of the last node.

Insertion and Deletion

• Insertion (heap)

  Insertion: consider inserting entry $(k,x)=(1,S)$ to the priority queue implement with a heap $T$. The insertion algorithm (insert(k,x)) is as follows:

  • Add a node $z$ to $T$ with operation add so that this new node becomes the last node of $T$ and stores entry $(k,x)$.
  • Restore the heap-order property that may be violated by the previous action.

  Link to original

• Up-heap bubbling

  Up-heap bubbling: After the insertion of a new entry with key $k$, the heap-order property may be violated. The algorithm up-heap restores the heap-order property by swapping entry with the key $k$ along an upward path from the insertion node. Up-heap terminates when the entry with key $k$ reaches the root or a node whose parent has a key smaller than or equal to $k$. Since the heap has a height $O(\log n)$, up-heap runs in $O(\log n)$ time.

  

  Link to original

• Deletion (heap)

  Deletion: the removal algorithm consists of three steps:

  • Replace the root element with the entry that is in the last node $w$.
  • Remove $w$.
  • Restore the head-order property.

  Link to original

• Down-heap bubbling

  Down-heap bubbling: after replacing the root element with the entry with key $k$ of the last node, the heap-order property may be violated. The algorithm down-heap restores the heap-order property by swapping the entry with key $k$ along a downward path from the root (swap the entry with key $k$ with its child with the smallest key). Down-heap terminates when key $k$ reaches a leaf or a node whose children have keys greater than or equal to $k$. Since the heap has a height $O(\log n)$, down-heap runs in $O(\log n)$ time.

  Link to original

Heap Sort

Consider a priority queue with $n$ items implemented by means of a heap:

• the space used is $O(n)$
• methods insert and removeMin take $O(\log n)$ time
• methods size, isEmpty and min take $O(1)$ time

Using a heap-based priority queue, we can sort a sequence of $n$ elements in $O(n\log n)$ time. The resulting algorithm is called a heap-sort.

Heap-sort is much faster than quadratic algorithms such as insertion or selection sorts which are backed by linear data structures.