Sorting Part A

Jesus A. Gonzalez

July 17, 2019

Heapsort

Heapsort

Heapsort

Heapsort

Heapsort

Heapsort

Heapsort

Heapsort

Heapsort

Heapsort

Maintaining the Heap Property

Maintaining the Heap Property

Maintaining the Heap Property

Maintaining the Heap Property

Building a Heap

Building a Heap

Building a Heap

Building a Heap

Building a Heap

Building a Heap

Loop Invariant for BUILD-MAX-HEAP

Loop Invariant for BUILD-MAX-HEAP

Loop Invariant for BUILD-MAX-HEAP

Loop Invariant for BUILD-MAX-HEAP

Upper Bound for BUILD-MAX-HEAP

A Tighter Bound for BUILD-MAX-HEAP

A Tighter Bound for BUILD-MAX-HEAP

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

\(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)\)

The Heapsort Algorithm

Heapsort

Heapsort

Heapsort

Heapsort

Heapsort

Heapsort

Heapsort

Priority Queues

Priority Queues

Priority Queues

Priority Queues

Priority Queues

Priority Queues

Priority Queues

Priority Queues