Heap

• Description:

  • Visualized as a tree, but is usually linear in storage (array, linked list)
  • Heap - Wikipedia (article)
  • Introduction - Coursera (video)
  • Naive Implementations - Coursera (video)
  • Binary Trees - Coursera (video)
  • Tree Height Remark - Coursera (video)
  • Basic Operations - Coursera (video)
  • Complete Binary Trees - Coursera (video)
  • Pseudocode - Coursera (video)
  • Heap Sort - jumps to start - Youtube (video)
  • Heap Sort - Coursera (video)
  • Building a heap - Coursera (video)
  • Heaps and Heap Sort - MIT 6.006 (video)
  • Priority Queues - UC Berkeley CS61B (video)
  • Linear Time BuildHeap (max-heap) - Youtube (video)

• Implement a max-heap:

  • insert
  • sift_up - needed for insert
  • get_max - returns the max item, without removing it
  • get_size() - return number of elements stored
  • is_empty() - returns true if heap contains no elements
  • extract_max - returns the max item, removing it
  • sift_down - needed for extract_max
  • remove(i) - removes item at index x
  • heapify - create a heap from an array of elements, needed for heap_sort
  • heap_sort() - take an unsorted array and turn it into a sorted array in-place using a max heap or min heap
    • note: using a min heap instead would save operations, but double the space needed (cannot do in-place).