A Beginner’s Guide to Binary Heaps

HeapSort

Heaps are actually very useful for sorting. Using buildHeap(), we can effectively build a heap in \(O(n)\) time, and then we can extract each minimum in the array in \(O(h)\) time. This means that we can extract every element in sorted order in \(O(n\log n)\).

std::vector<Element> sortAscending(std::vector<Element>& v) {
  MinHeap minh;
  minh.buildHeap(v);
  while(minh.arr.size() != 0) {
    minh.arr.push_back(minh.extractMin());
  }

  return minh.arr;
}

std::vector<Element> sortDescending(std::vector<Element>& v) {
  MaxHeap maxh;
  maxh.buildHeap(v);
  while(maxh.arr.size() != 0) {
    maxh.arr.push_back(maxh.extractMin());
  }

  return maxh.arr;
}

Questions?

If you have any questions or concerns, or if I have done something wrong, please leave a comment and let me know!