Exercise

  1. Please implement MaxPQ based on an unordered array and ordered array, respectively.
  1. Do exercise 1 using a linked list.
  1. Please prove that the height of a complete binary tree of size N is \(\lfloor \lg{N} \rfloor\).
  1. Please implement the minimum binary heap (MinPQ).
  1. Please design an algorithm to test whether a maximum binary heap is valid.
  1. Given the Book class, please compare books by the price first, and then by the length of titles if the prices are identical.
  1. Please implement the MaxPQ with a user-defined comparator in Python.
  1. Please implement a binary heap using explicit links. Hint: you shall use left, right, and parent as we did in a RBT.
  1. How to use PriorityQueue or heapq as a minimum heap?
  1. Please design an algorithm to sort a list based on the heap.
  1. Please give the time analysis for swim-based heap construction.