Heaps

Heaps and heapsort

Text

CLRS Chapter 6

ADT

• nearly complete binary tree
  • terminology: node, parent, child, left, right
• lowest level may be incomplete, but filled from left

Implement with an array

• how could you store a heap so that it is easy to access
  • left(i)
  • right(i)
  • parent(i)
• need to keep track of heapSize (vs. capacity)

Max-heap property

• A[parent(i)] >= A[i]

Operations

• maxHeapify(A,i)
• buildMaxHeap(A,i)

Heapsort

How can we use this data structure to sort?