Heap Sort

Chapter 5 – Part 3: Heaps • A heap is a binary tree structure such that: – The tree is complete or nearly complete. – The key value of each node is >= the key value of each of its descendents (max-heap).

1

Heap Properties • Completeness: Complete tree: N = 2H − 1 (last level is full) H = [log2N] + 1

Nearly complete:

All nodes in the last level are on the left A

B D

A C

B D

A C

E

B D

C E

F 2

Heap Properties • Key value order: 12

24 12

44 18

8 6

23 10

3

Insert Heap • Insert the new node into the bottom level, as far left as possible 12

24 12

44 18

8 6

23 10

• and then reheap-up 4

Basic Heap Operations 42

42

21

32

16 13

12 15

10

21

20

30

32

16

25

13

25 15

10

20

30

12

42

Reheapup

25

32

16 13

21 15

10

20

30

12 5

Delete Heap • replace the deleted value by the value X of the last leaf (rightmost in the last level) • delete the last leaf 78

10

21

32

16 13

12 15

10

20

21 30

16 13

32 12

20

30

15

• and then reheap-up, if X is ≥ its parent, or reheapdown, if X is < either of its children 6

Basic Heap Operations swap with the larger of its children

10 21 16 13

32 12

20

21 30

16

15

13

21 16 13

15

20

30

swap with the larger of its children

30 12

15

10 12

32

Reheapdow n

32

20

10

7

Heap Data Structure • Node i: left child 2i + 1, right 2i +2

78

[0 ]

56 45

[1 ]

[3 ]

32

8

23

[4 ]

[5 ]

[2 ]

• Node i: parent [(i − 1)/2] 19

[6 ]

• Left child j: right sibling j + 1 • Right child j: left sibling j − 1 • Heap size n: first leaf [n/2]

78

56

32

45

8

[0 ]

[1 [2 [3 ] ] ]

[4 ]

23

19

[5 [6 ] ]

• First leaf k: last nonleaf k − 1

8

ReheapUp Algorithm Algorithm reheapUp (ref heap <array>, val newNode ) Reestablishes heap by moving data in child up to its correct location Pre Post

heap is an array containing an invalid heap newNode is index location to new data in heap Heap has been restored

1 if (newNode not 0) 1 parent = (newNode − 1)/2 2 if (heap[newNode].key > heap[parent].key) 1 swap (newNode, parent) 2 reheapup (heap, parent) 2 return End

reheapUp

9

ReheapDown Algorithm Algorithm reheapDown (ref heap <array>, val root , val last ) Reestablishes heap by moving data in root down to its correct location Pre

Post

heap is an array containing an invalid heap root is root of heap last is an index to the last element in heap Heap has been restored

10

ReheapDown Algorithm 1

2

if (root*2 + 1 <= last) 1 leftKey = heap[root*2 + 1].data.key 2 if (root*2 + 2 <= last) 1 rightKey = heap[root*2 + 2].data.key 3 else 1 rightKey = lowKey 4 if (leftKey > rightKey) 1 largeChildKey = leftKey 2 largeChildIndex = root*2 + 1 5 else 1 largeChildKey = rightKey 2 largeChildIndex = root*2 + 2 6 if (heap[root].data.key < heap[largerChildIndex].data.key) 1 swap (root, largerChildIndex) 2 reheapDown (heap, largerChildIndex, last) return

End

reheapDown

11

Build Heap Algorithm buildHeap (ref heap <array>, val size ) Given an array, rearrange data so that it forms a heap Pre Post

heap is an array containing an invalid heap size is number of elements in array array is now a heap

1 walker = 1 2 loop (walker <= size) 1 reheapUp (heap, walker) 2 walker = walker + 1 3 return End

buildHeap

8

19

23

32

45

56

78

78

56

32

45

8

23

19

[0 ]

[1 [2 [3 ] ] ]

[4 ]

[5 [6 ] ] 12

Insert Heap Algorithm

insertHeap (ref heap <array>, ref last val data )

Inserts data into heap Pre

heap is a valid heap last is index to last node in heap Post data have been inserted into heap Return true if successful; false if array is full 1 if (heap full) 1 return false 2 last = last + 1 3 heap[last] = data 4 reheapUp (heap, last) 5 return true End

insertHeap 13

Delete Heap Algorithm

deleteHeap (ref heap <array>, ref last ref dataOut )

Deletes root of heap and passes data back to caller Pre

heap is a valid heap last is index to last node in heap dataOut is reference parameter for output data Post root has been deleted from heap Return true if successful; false if array is empty 1 if (heap empty) 1 return false 2 dataOut = heap[0] 3 heap[0] = heap[last] 4 last = last - 1 5 reheapDown (heap, 0, last) 6 return true End

deleteHeap

14

Complexity of Heap Operations

• ReheapUp: O(log2n)

• ReheapDown: O(log2n) • BuildHeap: O(nlog2n) • InsertHeap: O(log2n) • DeleteHeap: O(log2n) 15

Heap Applications • Selection Algorithms: to determine the kth largest element in an unsorted list – Creat a heap – Delete k - 1 elements from the heap – The desired element will be at the top

16

Heap Applications • Priority Queues: each element has a priority to be dequeued – Use a heap to represent a queue – Elements are enqueued according to their priorities – Top element is dequeued first

17