loading...

Binary Heaps

jjb profile image JB Updated on ・3 min read

CS Level Up Series (30 Part Series)

1) CS Level Up Series Introduction 2) Dynamic Arrays 3 ... 28 3) Linked Lists 4) Stacks 5) Queues 6) Hash Tables 7) Binary Search Trees 8) Binary Heaps 9) Priority Queues 10) Graphs 11) Tries 12) Binary & Bit Manipulation 13) Common Sorting Algorithms 14) Searching Algorithms 15) Permutations, Combinations, & Subsets 16) NP-Complete & Fibonacci Heap 17) Detecting Graph Cycles With Depth-First Search 18) Finding Shortest Paths In Graphs (using Dijkstra's & BFS) 19) Topological Sorting of Directed Acyclic Graphs (DAGs) 20) Finding Articulation Points & Bridges in Undirected Graphs 21) Finding Strongly Connected Components in Directed Graphs using Tarjan's Algorithm 22) Checking If An Undirected Graph Is Bipartite 23) Extending An Iterator 24) Union-find (Disjoint-set) 25) Minimum Spanning Tree (Kruskal's Algorithm) 26) Sliding Window Technique 27) String Searching Using Rabin-Karp 28) Fenwick Tree (Binary Indexed Tree) 29) Dynamic Programming 30) Traveling Salesman Problem

Resources

  1. Heap/Binary Heap Overview
  2. Binary Heap/Priority Queue Overview
  3. Another Binary Heap Overview
  4. Overview with implementation (missing heapsort)
  5. Heapsort implementation
  6. In depth detail of operations with diagrams + code for each
  7. Similar to previous, each page discusses a different aspect/operation + code
  8. In depth implementation

Takeaways (for min-heap, but the same applies to max-heap):

  • A binary heap is essentially a binary tree with either the smallest element at the top (min-heap), or the largest (max-heap).
  • The two common types of binary heaps are: min-heap and max-heap. But there are also more exotic variants like the min-max-heap
  • Retrieval of the smallest element in a min-heap is O(1) (constant).
  • Inserting an element and extracting the min element are O(log n) (logarithmic) operations.
  • Extracting the min element from a min-heap is O(log n). This is because a new root will need to be determined.
  • Heapify is a an operation that turns an array into a heap[0]. It is an O(n) operation.
  • Binary heaps are typically implemented using arrays. Space is O(n).
  • Heapsort is a sorting algorithm that transforms an input array into a heap, and then turns the resulting heap into a sorted collection[1].
  • Priority Queues are often implemented using binary heaps. Which makes sense given in my first post of this series, I link to a medium article that groups together binary heap and priority queue into one bullet point.

[0] Heapify is a common term, and therefore important to know. However, in my implementation I opted to refer to the heapify operation as PercolateDown instead. I had seen this terminology used elsewhere (both related, and not related, to heaps), and it reminded me of these exercises from Princeton (which I remember failing miserably years ago). It is also necessary to percolate elements up a heap when inserting or decreasing a key - so to me, having PercolateDown and PercolateUp functions makes sense.

[1] Heapsort does this in place, which means no additional memory is used to perform the sort. It does this by swapping elements around in the input array. (Technically extra space/memory is used for some temporary variables. But as long as the extra memory is O(log n) or less, an algorithm can still be considered in-place)

Overall, binary heaps took a bit of time to fully grasp but once I properly understood them I found the implementation relatively simple.

Please remember that simple != easy, this is best illustrated by a Shep Hyken cartoon:

Anyway, here's the finished implementation of a min-heap with some test code. A max-heap would look very similar - so if you can implement one, you will be able to implement the other:

As always, if you found any errors in this post please let me know!

CS Level Up Series (30 Part Series)

1) CS Level Up Series Introduction 2) Dynamic Arrays 3 ... 28 3) Linked Lists 4) Stacks 5) Queues 6) Hash Tables 7) Binary Search Trees 8) Binary Heaps 9) Priority Queues 10) Graphs 11) Tries 12) Binary & Bit Manipulation 13) Common Sorting Algorithms 14) Searching Algorithms 15) Permutations, Combinations, & Subsets 16) NP-Complete & Fibonacci Heap 17) Detecting Graph Cycles With Depth-First Search 18) Finding Shortest Paths In Graphs (using Dijkstra's & BFS) 19) Topological Sorting of Directed Acyclic Graphs (DAGs) 20) Finding Articulation Points & Bridges in Undirected Graphs 21) Finding Strongly Connected Components in Directed Graphs using Tarjan's Algorithm 22) Checking If An Undirected Graph Is Bipartite 23) Extending An Iterator 24) Union-find (Disjoint-set) 25) Minimum Spanning Tree (Kruskal's Algorithm) 26) Sliding Window Technique 27) String Searching Using Rabin-Karp 28) Fenwick Tree (Binary Indexed Tree) 29) Dynamic Programming 30) Traveling Salesman Problem

Posted on Nov 25 '19 by:

Discussion

markdown guide