7 Heaps

Heaps - Add elements quickly and query/remove the most important element quickly

7.1 Uses

  • getting the smallest/largest item each time in succession

  • maintaining top or bottom k elements, getting the median of large datasets

  • sorting data via heap sort

7.1.1 Pre reqs of the data

  • Has to be orderable

  • Has to have > implemented

7.1.2 ADT implementation functions

  • insert
  • remove
  • isEmpty

7.2 min heap vs max heap

  • min heap is smallest at top and higher at the bottom

  • max heap is the largest at top and goes smaller at the bottom

  • the logic is basically the same in either case, just inverted - we’ll do min heap here but the similar prinicples apply to max heap quite easily

7.3 Array based implementation

  • the simplest way to do it is with arrays that has each level contiguous

  • it makes swaps and indexing easy

  • not having to deal with pointers as much - we’re used to arrays

7.3.1 Compare to other implementations

  • unsorted

7.4 insert() - Heapify up

  • Add a bottom

7.5 Heapify down

7.6 Build heap

To build a Heap in linear time we heapify down from the bottom to the top

7.6.1 Recursive proof

7.7 Heap Sort

7.8 Priority Queue

7.9 See also: