Heapsort

• Running time \(O(n \lg n)\), like merge sort
• Sorts in place (as insertion sort), only constant number of array elements are stored outside the input array at any time
• Combines better attributes of these other sorting algorithms
• Uses an algorithm design technique: using a data structure, a heap
  • Heap also referred as garbage-collected storage
  • As in java and Lisp

Heapsort

• Binary heap data structure
  • Array object can be viewed as a nearly complete binary tree
  • Each node corresponds to an element of the array
  • Tree completely filled on all levels, except (possibly) the lowest
    • Lowest filled from the left up to a point

Heapsort

• Binary heap data structure
  • An array \(A\) represents the heap, an object with two attributes
    • \(A.length\), number of elements in the array
    • \(A.heap-size\), how many elements in the heap are stored within array \(A\)
    • \(A[1 .. A.length]\) may contain numbers but only elements in \(A[1 .. A.heap-size]\), where \(0 \leq A.heap-size \leq A.lenght\), are valid elements in the heap
  • Root of tree is \(A[1]\)
  • Given index \(i\) of a node, we can compute indices of its parent, left child, and right child

Heapsort

Heapsort

Heapsort

• Two kinds of binary heaps
• The values in the nodes satisfy the heap property
  • max-heaps
    • max-heap property
    • For every node \(i\) other than the root, \(A[PARENT(i)] \geq A[i]\)
    • The value of a node is at most the value of its parent
    • Largest element in a max-heap is stored at the root

Heapsort

• Two kinds of binary heaps
  • min-heaps
    • min-heap property
    • For every node \(i\) other than the root, \(A[PARENT(i)] \leq A[i]\)
    • The smallest element in a min-heap is at the root

Heapsort

• max-heaps are used for the heapsort algorithm
• min-heaps implement priority queues
• Viewing heap as a tree
  • height of a node in a heap \(\rightarrow\) number of edges on the longest simple downward path from the node to a leaf
  • height of a heap \(\rightarrow\) the height of its root
• A heap of \(n\) elements based on a complete binary tree
  • Height is \(\Theta( \lg n)\)
• Basic operations on heaps run in time proportional to the height of the tree
  • \(O( \lg n)\)

Heapsort

• MAX-HEAPIFY, runs in \(O( \lg n)\) time, key to mantain the max-heap property
• BUILD-MAX-HEAP, linear time, produces a max-heap from an unordered input array
• HEAPSORT, runs in \(O(n \lg n)\) time, sorts an array
• MAX-HEAP-INSERT, HEAP-EXTRACT-MAX, HEAP-INCREASE-KEY, and HEAP-MAXIMUM, run in \(O( \lg n)\) time
  • Used to implement a priority queue

Maintaining the Heap Property

• MAX-HEAPIFY used to maintain the max-heap property
  • Inputs: an array \(A\) and an index \(i\)
  • MAX-HEAPIFY assumes that binary trees rooted at LEFT(i) and RIGHT(i) are max-heaps, but that \(A[i]\) might be smaller than its children (violating the max-heap property)
    • MAX-HEAPIFY moves the value \(A[i]\) down in the max-heap so that subtree rooted at index \(i\) follows the max-heap property

Maintaining the Heap Property

Maintaining the Heap Property

Maintaining the Heap Property

• Running time of MAX-HEAPIFY on subtree of size \(n\) at node \(i\) is
  • \(\Theta(1)\) to fix up relationships among \(A[i]\), \(A[LEFT(i)]\), and \(A[RIGHT(i)]\)
  • Time to run MAX-HEAPIFY on subtree rooted at one children of node \(i\)
    • Children’s subtrees have size at most \(2n/3\)
    • Worst case when bottom level of tree is exactly half full
  • Running time of MAX-HEAPIFY with recurrence
    • \(T(n) \leq T(2n/3) + \Theta(1)\)
  • Solution to recurrence by case 2 of master theorem
    • \(T(n) = O( \lg n)\)

Building a Heap

• Use MAX-HEAPIFY bottom-up
  • Convert array \(A[1 .. n]\), \(n = A.length\), into a max-heap
  • Elements in the subarray \(A[(\lfloor n/2 \rfloor + 1) .. n]\) are the leaves of the tree
  • Each of these is a 1-element heap to begin with
• BUILD-MAX-HEAP(\(A\)) goes through remaining nodes of the tree
  • Runs MAX-HEAPIFY on each of them

Building a Heap

Building a Heap

Building a Heap

Building a Heap

Building a Heap

Loop Invariant for BUILD-MAX-HEAP

• Start of each iteration of for loop, lines 2-3, each node \(i + 1\), \(i + 2\), \(\dots\), \(n\) is the root of a max-heap
• Loop invariant shows
  • This invariant is true prior to first loop iteration
  • Each iteration of loop maintains the invariant
  • The invariant provides useful property to show correctness when the loop terminates

Loop Invariant for BUILD-MAX-HEAP

• Initialization: Prior to first iteration of loop
  • \(i = \lfloor n/2 \rfloor\).
  • Each node \(\lfloor n/2 \rfloor + 1\), \(\lfloor n/2 \rfloor + 2\), \(\dots\), \(n\) is a leaf and also the root of a trivial max-heap

Loop Invariant for BUILD-MAX-HEAP

• Maintenance: See that each iteration maintains the loop invariant
  • Children of node \(i\) numbered higher than \(i\), they are both roots of max-heaps
  • This is required by MAX-HEAPIFY(\(A\), \(i\)) to make node \(i\) a max-heap root
  • MAX-HEAPIFY(\(A\), \(i\)) preserves property that nodes \(i + 1\), \(i + 2\), \(\dots\), \(n\) are all roots of a max-heap
  • Decreasing \(i\) in for loop update, reestablishes loop invariant for next iteration

Loop Invariant for BUILD-MAX-HEAP

• Termination: at termination \(i = 0\)
  • By loop invariant, each node 1, 2, \(\dots\), \(n\) is the root of a max-heap
  • In particular, node 1, the root of the tree

Upper Bound for BUILD-MAX-HEAP

• Each call to MAX-HEAPIFY costs \(O( \lg n)\) time
• BUILD-MAX-HEAP makes \(O(n)\) such calls
• Running time is \(O(n \lg n)\)
• This upper bound is correct but not asymptotically tight

A Tighter Bound for BUILD-MAX-HEAP

• Time for MAX-HEAPIFY to run at a node varies with height of the node in the tree
• Heights of most nodes are small
• Tighter analysis uses properties that an \(n\)-element heap has height \(\lfloor lg n \rfloor\) and at most \(\lceil n/2^{h+1} \rceil\) nodes of any height \(h\)
• Time required by MAX-HEAPIFY when called on node of height \(h\) is \(O(h)\)
• Total cost of BUILD-MAX-HEAP: \(\sum_{h=0}^{\lfloor \lg n \rfloor} \lceil \frac{n}{2^{h+1}} \rceil O(h)\) \(= O \left( n \sum_{h=0}^{\lfloor \lg n \rfloor} \frac{h}{2^h} \right)\).

A Tighter Bound for BUILD-MAX-HEAP

• Evaluating summation by substituting \(x = 1/2\) in formula (A.8)

\(\sum_{h=0}^{\infty} \frac{h}{2^h} = \frac{1/2}{(1 - 1/2)^2} = 2\)

• We bound running time of BUILD-MAX-HEAP as

\(O \left( n \sum_{h=0}^{\lfloor \lg n \rfloor} \frac{h}{2^h} \right)\) \(=O \left( n \sum_{h=0}^{\infty} \frac{h}{2^h} \right)\) \(=O(n)\)

Heapsort

• Starts by using BUILD-MAX-HEAP on input array \(A[1 .. n]\), where \(n = A.length\)
  • Maximum element of array stored at root \(A[1]\), we can put it in its final position, exchanging it by \(A[n]\)
  • Now, the new root might violate the max-heap property, we restore it by calling MAX-HEAPIFY(\(A\), 1), that leaves a max-heap \(A[1 .. n-1]\)
  • The process is repeated for max-heap size \(n-1\) down to a heap of size 2

Heapsort

Heapsort

• Running time: \(O(n \lg n)\)
  • Call to BUILD-MAX-HEAP takes time \(O(n)\)
  • Each of \(n-1\) calls to MAX-HEAPIFY take \(O( \lg n)\)

Heapsort

Heapsort

Heapsort

Heapsort

Priority Queues

• Heapsort is a good sorting algorithm but quicksort usually beats it in practice
• The heap data structure has many uses
• A popular application of heaps is an efficient priority queue
• A priority queue can be max-priority or min-priority
• We focus on max-priority queues, based on max-heaps

Priority Queues

• A priority queue is a data structure that mantains a set \(S\) of elements, each with an associated value called a key. A max-priority queue supports the operations
  • INSERT(\(S, x\)): inserts element \(x\) into set \(S\), equivalent to \(S = S \cup \{x\}\)
  • MAXIMUM(\(S\)): returns the element \(S\) with the largest key
  • EXTRACT-MAX(\(S\)): removes and returns the element of \(S\) with the largest key
  • INCREASE-KEY(\(S, x, k\)): increases the value of element \(x\)’s key to new value \(k\), which is assumed to be as large as \(x\)’s current value

Priority Queues

• HEAP-MAXIMUM runs in \(\Theta(1)\) time

Priority Queues

• HEAP-EXTRACT-MAX runs in \(O( \lg n)\) time

Priority Queues

• HEAP-INCREASE-KEY runs in \(O( \lg n)\) time

Priority Queues

• MAX-HEAP-INSERT runs in \(O( \lg n)\) time

Priority Queues

Priority Queues

Quicksort

• Worst case \(\Theta(n^2)\)
• Average case with expected running time of \(\Theta(n \lg n)\)
  • A good practical choice, remarkably efficient on average
  • Constant factors hidden in \(\Theta(n \lg n)\) are quite small
• Performs sorting in place
• Works well even in virtual-memory environments

Description of Quicksort

• Applies divide-and-conquer to sort a subarray \(A[p .. r]\)
• Divide: Partition array \(A[p .. r]\) into two subarrays \(A[p .. q-1]\) and \(A[q+1 .. r]\)
  • Each element of \(A[p .. q-1]\) is less than or equal to \(A[q]\), which is less or equal to each element of \(A[q+1 .. r]\)
  • \(q\) is computed as part of the partitioning
• Conquer: Sort the two subarrays \(A[p .. q-1]\) and \(A[q+1 .. r]\) by recursive calls to quicksort
• Combine: Subarrays are already sorted, no work needed to combine them

Description of Quicksort

Description of Quicksort

• There exist different algorithms for partitioning

Description of Quicksort

• For the partitioning algorithm
  • Clear gray: lower elements partition
  • Dark gray: higher elements partition
  • Last element: pivot
  • White. unassigned elements

Description of Quicksort

Performance of Quicksort

• Depends on \(\dots\)
  • Whether the partition is or not balanced
  • What element was used to partition
  • Balanced partition
    • Fast as MergeSort
  • Unbalanced
    • Slow as InsertionSort

Performance of Quicksort

• Worst case partitioning (previously ordered input)
  • when partitioning produces 1 region with \(n-1\) elements and the other with 0 elements
  • Assumes that this happens in each step of the algorithm
  • Cost to partition \(\Theta(n)\)
  • Recursive call on array size 0 just returns, \(T(0) = \Theta(1)\) \(T(1) = \Theta(1)\)
  • Recurrence \(T(n) = T(n-1) + \Theta(n)\)
  • If we sum costs at each level of the recursion we get an arithmetic series (eq. A.2) that evaluates to \(\Theta(n^2)\)
  • \(T(n) = T(n-1) + \Theta(n)\) has solution \(T(n) = \Theta(n^2)\)

\(\sum_{k=1}^{n} k = \frac{1}{2} n(n+1)\) = \(\Theta(n^2)\)

Performance of Quicksort

• Best case in partition
  • Regions of size \(n/2\)
  • Recurrence \(T(n) = 2T(n/2) + \Theta(n)\)
  • Case 2, master theorem \(\leftarrow\) \(T(n) = \Theta(n \lg n)\)

Performance of Quicksort

• Average case closer to the best case than to the worst case
  • Suppose a split in proportion 9-1 \(\leftarrow\) looks too unbalanced
  • Recurrence \(T(n) = T(9n/10) + T(n/10) + n\)
  • See recursion tree

Performance of Quicksort

• Recursion tree, balanced split case

Performance of Quicksort

• Balanced partitioning
  • Each level has cost \(n\)
  • Boundary condition at depth \(\log_{10} n = \Theta( \lg n)\)
    • Levels have a cost at most \(n\)
  • Recursion ends at depth \(\log_{10/9} n = \Theta( \lg n)\)
  • Total cost of QuickSort \(\leftarrow\) = \(\Theta(n \lg n)\)
    • For each split with constant proportion

Performance of Quicksort

• Intuition for the average case
  • Partition produces good and bad splits
    • Randomly distributed
    • Suppose good and bad splits alternate (in the tree)
      • Good \(\rightarrow\) splits of the best case
      • Bad \(\rightarrow\) splits of the worst case
    • Running time is still \(\Theta(n \lg n)\)
      • With larger constant hidden by the \(O\)-notation