ds23 8

Chapter 5
Priority Queues (Heaps) and

Heapsort
COMP2015 HKBU/CS/JF/2023 1
Priority Queues - Motivation
v Have you ever been jammed by a huge job while you are
waiting for just one-page printout ?
3 jobs have been submitted to a printer in the order A, B, C.

Sizes: Job A – 100 pages
Job B – 10 pages
Job C -- 1 page
Average waiting time with FIFO service:
(100+110+111) / 3 = 107 time units
Average waiting time for shortest-job-first service:
(1+11+111) / 3 = 41 time units
Priority Queues - Motivation
v Need to have a queue which does insert and deletemin

- Priority Queue
n A priority queue is a data structure that has the following

property:
Finding or removing the smallest element is fast
n All jobs will be placed in the priority queue based on the

priority.
Priority Queues - Implementation
Method 1 – Linked List

Insert in O(1)
Find the minimum element in O(N),
thus deletion is O(N)
Method 2 – Binary Search Tree (BST)

Insert in O(logN)
Delete in O(logN)
Search tree is an overkill as it does many other operations.
Priority Queues - Implementation
n Binary heaps (Heaps) are “almost complete binary trees”.

-- All levels are full except possibly the lowest level.
q If the lowest level is not full, nodes must be packed to the
left.
A complete tree Almost complete tree
Completeness
Incomplete Complete
A A
C B C
B
D E F G D E F G
H I J H I J
Note: This is a stronger

This missing node property than a BST
makes the tree since it does not permit
incomplete. gaps in any rows.
Heap Structure Property
n Structure Property
q A heap is a binary tree that is completely filled, except at

the bottom level, which is filled from left to right.
q A heap of height h has 2h to (2h+1 – 1) nodes.
Heap Order Property
n Heap Order Property
q The value at any node should be smaller than (or equal
to) all of its descendants
q Guarantee that the node with the minimum value is at
the root). (Min-heap)
A heap Not a heap !!
Are these heaps?
INVALID
Binary Heap:
1. Binary Tree 1
2. Heap
3. Complete
3 VALID
INVALID 4
4 7
5 6
2 5 6
9 8 7
3 7 8
9 11 10
Heap: Array Implementation
n Array: “tree-like” arrangement (i) level by level, and (ii) left to
right
00
Note: The parent of any
This has a node i is given by i/2
special purpose
(integer division)
01
02 03
Note: The left Note: The right
child of any node child of any node
i is given by 2i 04 05 06 07 i is given by 2i
+1
08 09 10 11 12 13 14 15
Heap: Array Implementation
For any element at array position i:
q left child is at (2i)
1
A
q right child is at (2i +1)
3
2
C q parent is at (int) (i/2)
B
4 5 6 7
D E F G
8 9 10
H I J
It’s common to store

the heap size in element zero
A B C D E F G H I J
0 1 2 3 4 5 6 7 8 9 10 11 12 13
Heap Operations
n Insertion
n Add the new element to the lowest level
n Restore the min-heap property if violated:

q “bubble up”: if the parent of the element is larger than
the element, then interchange the parent and child.
n This strategy is called “percolate up”.
Insertion
while(A[i] < A[i/2])

{ swap(A[i],A[i/2]);
i = i/2;
}
Insert 4
Percolate up to maintain the heap property
Insertion
A heap!
v Worst case running time is O(logN) - The new element is

percolating up all the way to the root.
Heap Operations
Ø DeleteMin: delete the minimum item from the heap
1. Remove the root

2. Place the last item in the heap into the root and restore
the heap order property by “bubble down”
Ø This strategy is called “percolate down”.
min-heap property destroyed
DeleteMin
DeleteMin
Tutorial
v DeleteMin:
5
10 9
17 14 11 13
20 19 16 15 24 22 18
Tutorial
v DeleteMin:
5
18
9
10 9
18
11
17 14 11
18 13
20 19 16 15 24 22
Tutorial
v Insert 3:
4 7
5 8 10 9
11 13
Tutorial
v Insert 3:
Algorithm:
- Insert a node to ensure no gaps 2
- Fix heap
- Percolate UP
4
3 7
5 8
4
3 10 9
11 13 3
8
Tutorial
v Construct a min Heap by inserting the following values in
this order:
5, 10, 15, 20, 7, 2
5
2
10
7 15
25
Percolate Up
20 7
10 2
15
Percolate Up Percolate Up
Tutorial
v What is the running time?
v Insertion has a running time of O(log(n))

v If we insert n items…
v Building a tree (heap) takes O(nlog(n))
- Add a node, fix the heap, add a node, fix the heap…
v Do better?
- Add all nodes, fix heap all at once à BuildHeap
algorithm
BuildHeap
n Given an array of numbers, how do we convert it into a heap?
Iterate from element int(size/2) to element 1:

percolate down element i, making the subtree rooted at i a heap
7
Start at element
int(size/2) = 7
BuildHeap
BuildHeap
Tutorial
v Construct a min Heap with the following values by
BuildHeap algorithm:
12, 5, 11, 3, 10, 2, 9, 4, 8, 15, 7, 6
Tutorial
v [Heap Implementation]
How do we find the minimum node?
How do we find a node’s left child?
How do we find a node’s right child?
How do we find a node’s parent?
d-Heaps
Ø A d-heap is a certain kind of tree (similar to complete binary

tree), except that all nodes have d children.
3-heaps
Ø Heap supports the following operations efficiently

- Locate the current minimum in O(1) time
- Delete the current minimum in O(logN) time
Heapsort
n Heapsort relies on the properties of a heap data structure
to sort a data set.
(1) Build a binary heap of N elements

q The minimum element is at the top of the heap
(2) Perform N – 1 DeleteMin operations

q The elements are extracted in sorted order
(3) Record these elements
v Note that heapsort does not need two separate arrays; it

can use the same array for the heap and the sorted array.
Heapsort: no extra storage
n After each deleteMin, the size of heap shrinks by 1

q We can use the last cell just freed up to store the element
that was just deleted
Þ after the last deleteMin, the array will contain the
elements in decreasing sorted order
n To sort the elements in the decreasing order, use a min heap

n To sort the elements in the increasing order, use a max heap
q The parent has a larger element than the children
Heapsort - Example
n Sort {14, 16, 3, 4, 7, 9, 10, 2, 8, 1} in increasing order: use

max heap
(a) Build the heap (b) Delete 16 (c) Delete 14
Heapsort - Example
n Sort in increasing order
(d) Delete 10 (e) Delete 9 (f) Delete 8
Heapsort - Example
n Sort in increasing order
Heapsort – Example
As you delete
the root of the heap,
place the deleted
items at the end of
the array that stores
the heap.
Once all items have

been deleted, you
will have a sorted
array.

ds23 8

Uploaded by

Copyright:

Available Formats

ds23 8

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

ds23 8

Uploaded by

Copyright:

Available Formats

Chapter 5

Priority Queues (Heaps) and

3 jobs have been submitted to a printer in the order A, B, C.

v Need to have a queue which does insert and deletemin

n A priority queue is a data structure that has the following

Finding or removing the smallest element is fast

n All jobs will be placed in the priority queue based on the

Method 1 – Linked List

Method 2 – Binary Search Tree (BST)

n Binary heaps (Heaps) are “almost complete binary trees”.

A complete tree Almost complete tree

Note: This is a stronger

q A heap is a binary tree that is completely filled, except at

q A heap of height h has 2h to (2h+1 – 1) nodes.

A heap Not a heap !!

It’s common to store

n Add the new element to the lowest level

n Restore the min-heap property if violated:

n This strategy is called “percolate up”.

while(A[i] < A[i/2])

Percolate up to maintain the heap property

v Worst case running time is O(logN) - The new element is

1. Remove the root

min-heap property destroyed

v What is the running time?

v Insertion has a running time of O(log(n))

Iterate from element int(size/2) to element 1:

How do we find a node’s left child?

How do we find a node’s right child?

How do we find a node’s parent?

Ø A d-heap is a certain kind of tree (similar to complete binary

Ø Heap supports the following operations efficiently

(1) Build a binary heap of N elements

(2) Perform N – 1 DeleteMin operations

(3) Record these elements

v Note that heapsort does not need two separate arrays; it

n After each deleteMin, the size of heap shrinks by 1

n To sort the elements in the decreasing order, use a min heap

n Sort {14, 16, 3, 4, 7, 9, 10, 2, 8, 1} in increasing order: use

(a) Build the heap (b) Delete 16 (c) Delete 14

n Sort in increasing order

(d) Delete 10 (e) Delete 9 (f) Delete 8

n Sort in increasing order

Once all items have

You might also like