basecs
Published in

basecs

Learning to Love Heaps

Learning to love heaps!

Rules before you heap

Heaps are a great example of many core computer science concepts working together in order to form one very large abstraction, which is made up of smaller parts that we’re already familiar with!

Heaps: a defintion
The two rules of heaping: shape + order.
Min heaps vs. max heaps

Growing and shrinking a heap

We must always maintain the shape and structure of a heap — otherwise, we’re violating one of its two properties!

Growing a heap: adding an element.
Shrinking a heap: removing an element
Shrinking a heap, continued: removing an element

Just as we percolated a node up to its correct location in the heap when we added an element, we will bubble down a node to an appropriate spot when we delete an element from the heap.

Queuing up heaps on heaps

When it comes to heaps, form truly does follow function.

Representing a heap as an array structure
Transforming heaps into arrays [EDIT: please notice that the number 4 is missing! I should have drawn it in (oops). It should be the right child of 19!]
Determining a node’s index in an array
Priority queues are queue data structures with additional properties.
Binary heaps are efficient ways of implementing priority queues!

Resources

  1. Heaps and Priority Queues, Hacker Earth
  2. Introduction to a Heap, Paul Programming
  3. Binary Heaps, Professor Victor S.Adamchik
  4. Priority Queues (Heaps), Professor Ananth Kalyanaraman
  5. Priority Queues, Professor Mary K. Vernon
  6. Priority Queue, GeeksforGeeks

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store