Heaps

Question 1

What is the basic definition of a heap?

Answer 1

A heap is really nothing more than a binary tree with some additional rules that it has to follow. These two rules are the two properties that define what differentiates a heap structure from any other tree structure.

1. It must have all of it’s nodes in a specific order ( greater-than/equal-to or less-than/equal-to) (max or min heap)
2. It’s shape must be complete ( every single level of the tree must be completely filled — with the last level being the only exception. Additionally, the last level of the tree must always have the left-most nodes filled first.)

Question 2

Why do we use an array to represent a Heap?

Answer 2

Binary heaps are super efficient for implementing priority queues because it’s very easy to know and retrieve/remove the element with the highest priority: it will always be the root node!

Question 3

How can you tell what the children are of the parent node?

Answer 3

If i = index of a parent node…
2i + 1 = index of left child node
2i + 2 = index of right child node

Question 4

How can you find the index of current node’s parent?

if n = index of current node?

Answer 4

(n - 1) / 2

Question 5

What are heaps used for?

Answer 5

Priority Queues…
Heaps are the very abstractions that we are (inadvertently) interacting with when we uses libraries to help us handle job scheduling, background workers, and even what our machines use to handle internal tasks!