Priority Queues and Heaps

Priority Queue ADT

• A priority queue stores a collection of entries; each entry is a key-value pair.
• The main methods include insert(k, x), which inserts an entry with key 'k' and value 'x', and removeMin(), which removes and returns the entry with the smallest key.
• Additional methods are min() to return (but not remove) an entry with smallest key, and size() and isEmpty() to check the queue's state.
• Priority queues can be applied for standby flyers, auctions, and the stock market.

Implementing Priority Queue with Linked Lists

• Can be implemented with an unsorted or a sorted list
• In an unsorted list, insert operations take O(1) time, while removeMin and min take O(n) time.
• In a sorted list, insert operations require O(n) time to find the insertion point, while removeMin and min take O(1) time because the smallest key is at the beginning.

Heaps as Trees

• Heaps are useful for efficient implementations

Heap Data Structure

• An array can be viewed as a nearly complete binary tree, physically as a linear array and logically as a binary tree.
• Array elements map to tree nodes, where the root is A[1], left child of A[i] is A[2i], right child is A[2i+1], and parent is A[⌊i/2⌋].
• length[A] is the number of elements in array A, heap-size[A] is the number of elements stored in the heap within A, and heap-size[A] ≤ length[A].

Heap Property (Max and Min)

• Max-Heap: the value of every node (excluding the root) is "at most" that of its parent, A[parent[i]] >= A[i], and the largest element is stored at the root.
• Min-Heap: the value of every node (excluding the root) is "at least" that of its parent, A[parent[i]] <= A[i], and the smallest element is stored at the root.
• In a max-heap, no values in any subtree are larger than the value stored at the subtree root, and the converse is true for min-heaps.

Height of Node and Heap

• The height of a node in a tree is the count of edges on the longest simple path from the node to a leaf.
• The height of a tree is the height of its root.
• The height of a heap is ⌊log n⌋, and basic heap operations run in O(log n) time.

Heapsort

• Heapsort combines merge sort and insertion sort attributes, with merge sorts better time complexity and insertion sorts "in place" sorting.
• Involves building a data structure (heap) to manage information, allowing for priority queues.
• Heapsort's running time is O(n lg n), sorts in place (unlike merge sort), and uses max-heaps for sorting

Steps in sorting

• Heapsort converts a given array of size 'n' to a max-heap with BuildMaxHeap, then swaps the first and last elements.
• This puts the largest element in its sorted position and leaves "n – 1" unsorted elements
• The array of the first "n – 1" elements will no longer be a max-heap and the element at the root is floated down its subtrees with MaxHeapify.
• Step 2 is repeated until sorted.

Heap Characteristics

• Height: ⌊log n⌋ (floor of log n)
• Number of leaves: ⌈n/2⌉ (ceiling of n/2)
• Number of nodes of height h: ≤ ⌈n/2^(h+1)⌉

Maintaining the heap property

• If two subtrees are max-heaps, but the root violates the max-heap property, fix by swapping with the larger of its children.
• This may cause a subtree to not be a heap, which must be recursively fixed

Procedure MaxHeapify

• In MaxHeapify(A, i) if left(i) or right(i) exist and are larger than A[i], it identifies the largest of A[i], A[left(i)], and A[right(i)], then exchanges A[i] with the largest

Running Time for MaxHeapify(A, n)

• MaxHeapify takes O(h) time, where 'h' is the height of the node where MaxHeapify is applied
• The worst-case running time alternates to T(n) = O(log n).

Building a heap

• Use MaxHeapify to convert an array A into a max-heap and will call MaxHeapify on each element in a bottom-up manner

Building a heap Algorithm - BuildMaxHeap(A)

• heap-size[A] is set to length[A].
• The algorithm iterates backwards from [length[A]/2] down to 1 and executes MaxHeapify(A, i).

Correctness of BuildMaxHeap

• At the start of each for loop iteration, the node i + 1, i + 2, ... n is the root of a max-heap and before the first iteration i = ⌊n/2⌋.
• Algorithm maintains subtrees as children of node i are max-heaps and MaxHeapify(i) renders node i a max heap root.
• MaxHeapify will renders node i a max heap while preservingthe heap root property of larger nodes

Running Time of BuildMaxHeap

• The loose upper bound is O(n log n) and follows this equation = Cost of a MaxHeapify call × No. of calls to MaxHeapify.
• The cost of a call to MaxHeapify at a node depends on the height, h, of the node - O(h)
• The tighter bound height of nodes h ranges from 0 to log n⌋, the number of nodes is from is [n/2^(h+1)] which will result in O(n), and the heap from an unordered array can be built in O(n)

Heapsort Algorithm

• Sorts by maintaining unsorted elements as a max-heap by building a max-heap on all elements of A
• Exchanges A[1] with A[n]

HeapSort(A) procedure

• The input A is converted into into a max-heap with Build-Max-Heap(A).
• The algorithm iterates through length[A] down to 2, exchanging A[1] with A[i], reducing the size of heap-size[A] and applies MaxHeapify(A, 1)

Algorithm Analysis

• Heapsort sorts in place and is not stable.
• Build-Max-Heap takes O(n) time, and each of the n-1 calls to MaxHeapify takes O(log n) time

Heap Procedures for sorting

• MaxHeapify is O(log n)
• BuildMaxHeap takes O(n)
• HeapSort takes O(n log n)

Priority Queue

• An important application of heaps is Priority Queues and are either Max or min
• Each set element has a key which is the element associated value. and ensures insertion and extraction efficiency.

Priority Queue Applications

• Can be used to ready a list of processes in operating systems by their priorities
• Can be used in event-driven simulators which maintain a list of events based on their time of occurrence

Basic Operations on a Max-Priority Queue

• Insert(S,x) - Inserts the element 'x' into the set 'S', S ← S ∪ {x}
• Maximum(S) retrieves the element of 'S' with the largest key.
• Extract-Max(S) removes then retrieves the element of 'S' having the largest key.
• Increase-Key(S,x,k) increments the value of element x's key with new value k.

Min-Priority Queue support

• Min-priority queue supports Insert, Minimum, Extract-Min, and Decrease-Key
• A heap offers a compromise between fast insertion and somewhat slower extraction.

Heap-Extract-Max(A) procedure

• Checkif heap-size[A] < 1 if so then there is a heap underflow error.
• max= A[1], set A[1] to be the heap-size[A], after the set heap-size[A] to heap-size[A] - 1
• After will execute MaxHeapify(A, 1) and return max.
• The running time of this procedure is O(log n)

Heap-Insert(A, Key) procedure

• In the Heap-Insert (A, Key) procedure "heap-size[A] = heap-size[A] + 1" and set i = heap-size[A]
• A while loop will occur so long as i > 1 and A[Parent(i)] <key ,
• Executes do A[i] =A[Parent(i)] after i=parent(i), when no longer true A[i] = Key.
• The running time of the procedure is O(log n)

Heap-Increase-Key(A, i, key) procedure

• if key < A[i] then generates an error ("new key is smaller than current key").
• The algorithm sets A[i] = key
• Executes a while function while i > 1 and A[Parent[i]] < A[i], then exchanges A[i] with A[Parent[i]] and sets i = Parent[i]