Table of Contents

Vocabulary

Priority Queues Key-Value Pairs Key Binary Heap Max Heap Min Heap Node Root Node Parent Nodes Child Nodes Ancestor Nodes Insertion Heapify Up Popping/Removing The Max Removing A Node Changing + Updating A Key

What Is A Priority Queue?

<aside> 💡 Sometimes data must be organized by priority. At a hospital, you would attend to patients with the most severe conditions. You might prioritize studying for your Data Structures exam over watching YouTube since that is a task of high importance to you.

Priority Queues are data structures that organize data by priority through Key-Value Pairs. The key represents the level of priority some value has. A binary heap is a kind of priority queue that comes in two types: max heaps or min heaps.

Here, we will explore the organization of binary heaps as well as their methods and the runtime of those methods.

</aside>

Max Heaps

<aside> 💡 A max heap organizes data where higher keys have the most priority. All of the keys are stored as nodes in the heap. The highest key of the max heap is the root node.

</aside>

IMG_B27E4A735E8A-1.jpeg

<aside> 💡 Parent nodes are predecessor nodes that may have child nodes, successor nodes below the parent. Parent nodes are also known as ancestor nodes. In the drawing above, 80 is the parent node. 70 and 60 are child nodes of 80.

</aside>

Requirements of Max Heaps

<aside> 💡 For a given data structure to be deemed a max heap:

  1. Each parent/ancestor node is $\ge$ its children nodes.
  2. Every row is full except the right hand side of the last row. Fullness is determined by $2^{row \space number}$.

</aside>

Example of Max Heap That Meet Requirements

IMG_C33167496CBE-1.jpeg

Examples of Max Heaps That Don’t Meet Requirements

IMG_9EB762CD2000-1.jpeg

Number of Rows In Heaps

<aside> 💡 If there are $n$ keys in a heap, how many rows does the heap have? This can be determined with the following formulas.

</aside>

$$ r = \lceil log_2 \space n \rceil \newline

r = 1 + last \space row \newline where \space last \space row = log_2(n+1)-1

$$

<aside> 💡 Thus, a heap has $\lceil log_2 \space n \rceil$ rows.

</aside>

IMG_16B41DF015CA-1.jpeg