A priority queue.

The most common implementation of a priority queue is the binary heap.

Binary Heap

Week 7

A Binary Heap is a complete binary tree which satisfies the heap two fundamental properties:

​

​

A Binary Heap is a complete binary tree which satisfies the heap two fundamental properties:

​

• Completeness: All of the tree's levels are filled in, with one possible exception of the highest level, which is supposed to be completed from left to right.

​

​

A Binary Heap is a complete binary tree which satisfies the heap two fundamental properties:

​

• Completeness: All of the tree's levels are filled in, with one possible exception of the highest level, which is supposed to be completed from left to right.

​

• Heap Property: Ensures that the node values are in order. The Min-Heap property (The smallest element is always at the root)

​

which avoids a child node from having a value smaller than its parent node.

Binary Heaps

​

1. Every level is full, last one from left to right

​

• Heap Property: No child is smaller than its parent

Insert (step 1)

Binary Heaps

​

• Every level is full, last one from left to right

​

• Heap Property: No child is smaller than its parent

Insert (step 2)

Binary Heaps

​

• Every level is full, last one from left to right

​

• Heap Property: No child is smaller than its parent

Insert (step 3)

Binary Heaps

​

• Every level is full, last one from left to right

​

• Heap Property: No child is smaller than its parent

What happens when we want to send the most important message?

Binary Heaps

​

• Every level is full, last one from left to right

​

• Heap Property: No child is smaller than its parent

What happens when we want to send the most important message?

ExtractMin (step 1)

Binary Heaps

​

• Every level is full, last one from left to right

​

• Heap Property: No child is smaller than its parent

What happens when we want to send the most important message?

ExtractMin (step 2)

Binary Heaps

​

• Every level is full, last one from left to right

​

• Heap Property: No child is smaller than its parent

What happens when we want to send the most important message?

ExtractMin (step 3)

Binary Heaps

​

• Every level is full, last one from left to right

​

• Heap Property: No child is smaller than its parent

What happens when we want to send the most important message?

ExtractMin (step 4)

Binary Heaps

​

• Every level is full, last one from left to right

​

• Heap Property: No child is smaller than its parent

Maybe when a message hasn't been sent for a while, we want to give it a smaller key and therefore a higher priority.

Binary Heaps

​

• Every level is full, last one from left to right

​

• Heap Property: No child is smaller than its parent

Maybe when a message hasn't been sent for a while, we want to give it a smaller key and therefore a higher priority.

Binary Heaps

​

• Every level is full, last one from left to right

​

• Heap Property: No child is smaller than its parent

Maybe when a message hasn't been sent for a while, we want to give it a smaller key and therefore a higher priority.

DecreaseKey (step 1)

Binary Heaps

​

• Every level is full, last one from left to right

​

• Heap Property: No child is smaller than its parent

Maybe when a message hasn't been sent for a while, we want to give it a smaller key and therefore a higher priority.

DecreaseKey (step 2)

O(1)

O(log n)

O(log n)

O(log n)

For any given element at position i, its:

​

• Left Child will be at position 2*i + 1
• Right Child will be at position 2*i + 2
• Parent Node will be at position (i-1)/2 (using integer division)

Initialization and Structure

Inserting a Key

O(log n)

Getting the Minimum

O(1)

Extracting the Minimum

O(log n)

DecreaseKey

O(log n)