BINARY

PRIORITY QUEUES
HEAPS
FULL BINARY TREE
Every non-leaf node has two children
All the leaves are on the same level

Full Binary Tree

 COMPLETE BINARY TREE
A binary tree that is either full or full through the
next-to-last level
The last level is full from left to right (i.e., leaves
are as far to the left as possible)

Complete Binary Tree

BINARY HEAPS
A binary heap is a partially ordered complete binary tree
 The tree is completely filled on all levels except possibly the lowest.

root 0

3 2

4 5

In a more general d-Heap

 A parent node can have d children
We simply refer to binary heaps as heaps

9
PROPERTIES OF BINARY HEAP

It is a binary tree with the following properties:

Structure Property : it is a complete binary tree
Heap order property: the value stored at a
node is lesser or equal to the values stored at
the children (Min heap
property)
HEAP IMPLEMENTATION USING
ARRAY REPRESENTATION
A heap is a complete binary tree, so it is easy to be
implemented using an array representation
ARRAY-BASED REPRESENTATION OF
BINARY TREES (CONT.)
 Parent-child relationships:
left child of nodes[i] = nodes[2*i+1]
right child of nodes[i] = nodes[2*i+2]
parent node of nodes[i] = nodes[(i-1)/2]
(int division-truncate)
 Leaf nodes:
nodes[numElements/2] to nodes[numElements - 1]
 BASIC OPERATIONS
Insert a node – Percolate Up
Delete a node – Percolate Down
Decrease key, Increase key, Remove key
Build the heap

13
BASIC HEAP OPERATIONS: INSERT(X)
Maintain the complete binary tree property and fix any problem with
the partially ordered tree property
 Create a leaf at the next available position
 Repeat
 Locate parent
 if heap order property not satisfied
 Swap with parent
 else
 Stop
 Insert x into its final location

14
 PERCOLATE UP – INSERT A
NODE
A hole is created at the bottom of the tree, in the
next available position.

10
12

15 17 18 23

20 19 34
15
 PERCOLATE UP
Insert 20
6

10
12

15 17 18 23

21 19 34 20

16
 PERCOLATE UP
Insert 16
6

10
12

15 18 23

21 19 34 17

17
 PERCOLATE UP
6

10
12

15 16 18 23

21 19 34 17

Complexity of insertion: O(logN) 18

INSERTION EXAMPLE: INSERT(14)

14

14

14

19
BASIC HEAP OPERATIONS: DELETEMIN()
Replace root with the last leaf ( last element in the array
representation
 This maintains the complete binary tree property but
may violate the partially ordered tree property
Repeat
 Find the smaller child of the “hole”
 If Partially Ordered Tree not satisfied
 Swap hole and smaller child
 else
 Stop

20
 DELETE A NODE -
PERCOLATE DOWN –
Delete minimum i-e 6
6

10
12

15 16 18 23

21 19 34 17

21
 PERCOLATE DOWN
Last element - 17. The hole at the root.

10
16

15 16 18 23

21 19 34 17

We try to insert 17 in the hole by percolating the hole down

22
 PERCOLATE DOWN
17 10

16

15 16 18 23

21 19 34

23
 PERCOLATE DOWN
10

15
17 16

16 18 23

21 19 34

24
 PERCOLATE DOWN
10

15
16

17 16 18 23

21 19 34

Complexity of deletion: O(logN)

25
DELETEMIN()
EXAMPLE 2 31

13 14 16 19 21 19 68 65 26 32 31

26
DELETEMIN() EXAMPLE (CONT’D)
31

31

31

27
OTHER HEAP OPERATIONS
1. DecreaseKey(p,d)
increase the priority of element p in
the heap with a positive value d.
percolate up.
2. IncreaseKey(p,d)
decrease the priority of element p in
the heap with a positive value d.
percolate down.
28
 OTHER HEAP OPERATIONS
3. Remove(p)
a. Assigning the highest priority to p - percolate p
up to the root.
b. Deleting the element in the root and filling the
hole by percolating down and trying to insert the
last element in the queue.

4. BuildHeap
input N elements
 place them into an empty heap through successive
inserts. The worst case running time is O(NlogN).
29
 BUILD HEAP - O(N)
Given an array of elements to be
inserted in the heap,

treat the array as a heap with

order property violated,

and then do operations to fix the

order property.
30
EXAMPLE:
150 80 40 30 10 70 110 100 20 90 60 50 120 140
130

150

80 40

70 110
30 10

100 20 90 60 50 120 140 130

31
 EXAMPLE (CONT)
After processing Level 2
150

80 40

Level 2 20 10
50 110

100 30 90 60 70 120 140 130

32
 EXAMPLE (CONT)
After processing Level 1
150

Level 1 10 40

50 110
20 60

100 30 90 80 70 120 140 130

33
 EXAMPLE (CONT)
After processing Level 0
Level 0
10

20 40

50 110
30 60

100 150 90 80 70 120 140 130

34
TIME COMPLEXITY - HEAP
Find max/min: O(1)

Delete max/min: O(logN)

Insert max/min: O(logN)

A heap is a useful data structure when you need to remove

the object with the highest (or lowest) priority.
LEFTIST HEAP
 Motivation – LEFTIST HEAP
• A binary heap provides O(log n) inserts and
O(log n) deletes but suffers from O(n log n)
merges
• A leftist heap offers O(log n) inserts and O(log
n) deletes and O(log n) merges
• Note, however, leftist heap inserts and deletes
are more expensive than Binary Heap inserts
and deletes
 Definition
A Leftist (min)Heap is a binary tree that satisfies the follow-
ing conditions. If X is a node and L and R are its left and
right children, then:
1. X.value ≤ L.value
2. X.value ≤ R.value
3. null path length of L ≥ null path length of R

where the null path length of a node is the shortest distance

between from that node to a descendant with 0 or 1 child.
If a node is null, its null path length is −1.
Example: Null Path Length
4

8 19

12 27 20

15 25 43
node 4 8 19 12 15 25 27 20 43
npl 1 0 1 1 0 0 0 0 0
Example: Null Path Length
4

8 0 19 1
What is the npl of the
right child of 8?
12 1 27 0 20 0

What are the npl’s of

15 0 25 the children of 20 and
0 43 0 the right child of 27?

node 4 8 19 12 15 25 27 20 43
npl 1 0 1 1 0 0 0 0 0
Example: Null Path Length
•node 4 violates leftist heap property
4  fix by swapping children

8 0 19 1

12 1 27 0 20 0

15 0 25 0 43 0

node 4 8 19 12 15 25 27 20 43
npl 1 0 1 1 0 0 0 0 0
 Leftist Heap
4

19 1 8 0

27 0 20 0 12 1

43 0 15 0 25 0

node 4 8 19 12 15 25 27 20 43
npl 1 0 1 1 0 0 0 0 0
 MERGING IN LEFTIST HEAP
merge(h1,h2):
Input: two leftist heaps h1 and h2
Output: leftist heaps resulting from the merge of h1 and h2
Algorithm:
// make sure that the root of h1 is ot larger than the root of h2
if h1.key > h2.key then swap(h1,h2)
// now, root of h1 is the root of the merged heap; merge the rest of h1 with h2
if h1.right=nil then
h1.right <-- h2
else
h1.right <-- merge( h1.right, h2 )
// make sure the leftist property is preserved: npl of left >= npl of right
if h1.left.npl < h1.right.npl then
swap( h1.left, h1.right )
// adjust npl of the root - since npl of right child is never greater than left, it is 1+npl of right
child
h1.npl <-- h1.right.npl + 1
return h1
 Merging Leftist Heaps
Consider two leftist heaps …

4 6

19 8 8 7

27 20 12 14

43 15 25

Task: merge them into a single leftist heap

 Merging Leftist Heaps
4 6

19 8 8 7

27 20 12 14

43 15 25

First, instantiate a Stack

 Merging Leftist Heaps
x y
4 6

19 8 8 7

27 20 12 14

43 15 25

Compare root nodes

merge(x,y)
 Merging Leftist Heaps
x y
4 6

19 8 8 7

27 20 12 14

43 15 25

Remember smaller value

 Merging Leftist Heaps
y
4 x 6

19 8 8 7

27 20 12 14

43 15 25

Repeat the process with the right

child of the smaller value
 Merging Leftist Heaps
y
4 x 6

19 8 8 7

27 20 12 14

43 15 25

6
4

Remember smaller value

 Merging Leftist Heaps
4 x 6
y
19 8 8 7

27 20 12 14

43 15 25

6
4

Repeat the process with the right

child of the smaller value
 Merging Leftist Heaps
4 x 6
y
19 8 8 7

27 20 12 14

43 15 25

7
6
4

Remember smaller value

 Merging Leftist Heaps
4 x 6

19 8 8 7
y
27 20 12 14
null
43 15 25

7
6
4

Repeat the process with the right

child of the smaller value
 Merging Leftist Heaps
4 x 6

19 8 8 7

27 20 12 14

43 15 25

8
7
6
4

Because one of the arguments is

null, return the other argument
 Merging Leftist Heaps
4 6

19 Refers to node 8 8 7 x
27 20 14 8

43 12
8
15 25
7
6
4

Make 8 the right child of 7

 Merging Leftist Heaps
4 6

19 Refers to node 8 8 7

27 20 14 8

43 12
8
15 25
7
6
4

Make 7 leftist (by swapping children)

 Merging Leftist Heaps
4 6

19 Refers to node 8 8 7

27 20 14 8

43 12

15 25
7
6
4

Return node 7
 Merging Leftist Heaps
4 6

19 Refers to node 8 8 7

27 20 14 8

43 12

15 25
7
6
4

Make 7 the right child of 6

(which it already is)
 Merging Leftist Heaps
4 6

19 Refers to node 8 8 7

27 20 14 8

43 12

15 25
7
6
4

Make 6 leftist (it already is)

 Merging Leftist Heaps
4 6

19 Refers to node 8 8 7

27 20 14 8

43 12

15 25

6
4

Return node 6
 Merging Leftist Heaps
4

19 6

27 20 8 7

43 14 8

12

15 25

6
4

Make 6 the right child of 4

 Merging Leftist Heaps
4

19 6

27 20 8 7

43 14 8

12

15 25

6
4

Make 4 leftist (it already is)

 Final Leftist Heap
4

19 6

27 20 8 7

43 14 8

12

15 25

• Verify that the tree is heap

4
• Verify that the heap is leftist
Return node 4
 Analysis
• Height of a leftist heap ≈ O(log n)
• Maximum number of values stored in Stack
≈ 2 * O(log n) ≈ O(log n)
• Total cost of merge ≈ O(log n)
 Inserts and Deletes
• To insert a node into a leftist heap, merge
the leftist heap with the node
• After deleting root X from a leftist heap,
merge its left and right subheaps
• In summary, there is only one operation, a
merge.
Skew Heaps
 Motivation
• Simplify leftist heap by
– not maintaining null path lengths
– swapping children at every merge step
 Definition
A Skew (min)Heap is a binary tree that satisfies the follow-
ing conditions. If X is a node and L and R are its left
and right children, then:
1. X.value ≤ L.value
2. X.value ≤ R.value

A Skew (max)Heap is a binary tree that satisfies the follow-

ing conditions. If X is a node and L and R are its left
and right children, then:
1. X.value ≥ L.value
2. X.value ≥ R.value
 Merging Skew Heaps
Consider two skew heaps …

4 6

19 8 8 7

27 20 12 14

43 15 25

Task: merge them into a single skew heap

 Merging Skew Heaps
4 6

19 8 8 7

27 20 12 14

43 15 25

First, instantiate a Stack

 Merging Skew Heaps
x y
4 6

19 8 8 7

27 20 12 14

43 15 25

Compare root nodes

merge(x,y)
 Merging Skew Heaps
x y
4 6

19 8 8 7

27 20 12 14

43 15 25

Remember smaller value

 Merging Skew Heaps
y
4 x 6

19 8 8 7

27 20 12 14

43 15 25

Repeat the process with the right

child of the smaller value
 Merging Skew Heaps
y
4 x 6

19 8 8 7

27 20 12 14

43 15 25

6
4

Remember smaller value

 Merging Skew Heaps
4 x 6
y
19 8 8 7

27 20 12 14

43 15 25

6
4

Repeat the process with the right

child of the smaller value
 Merging Skew Heaps
4 x 6
y
19 8 8 7

27 20 12 14

43 15 25

7
6
4

Remember smaller value

 Merging Skew Heaps
4 x 6

19 8 8 7
y
27 20 12 14
null
43 15 25

7
6
4

Repeat the process with the right

child of the smaller value
 Merging Skew Heaps
4 x 6

19 8 8 7

27 20 12 14

43 15 25

8
7
6
4

Because one of the arguments is

null, return the other argument
 Merging Skew Heaps
4 6

19 Refers to node 8 8 7 x
27 20 14 8

43 12
8
15 25
7
6
4

Make 8 the right child of 7

 Merging Skew Heaps
4 6

19 Refers to node 8 8 7

27 20 14 8

43 12
8
15 25
7
6
4

Swap children of node 7

 Merging Skew Heaps
4 6

19 Refers to node 8 8 7

27 20 14 8

43 12

15 25
7
6
4

Return node 7
 Merging Skew Heaps
4 6

19 Refers to node 8 8 7

27 20 14 8

43 12

15 25
7
6
4

Make 7 the right child of 6

(which it already is)
 Merging Skew Heaps
4 6

19 Refers to node 8 7 8

27 20 8 14

43 12

15 25

7
6
4

Swap children of node 6

 Merging Skew Heaps
4 6

19 Refers to node 8 7 8

27 20 8 14

43 12

15 25

6
4

Return node 6
 Merging Skew Heaps
4

19 6

27 20 7 8
8 14
43
12

15 25

6
4

Make 6 the right child of 4

 Merging Skew Heaps
4
6 19

7 8 27 20
8 14 43
12

15 25

6
4

Swap children of node 4

 Final Skew Heap
4
6 19

7 8 27 20
8 14 43
12

15 25

• Verify that the tree is heap

4
• Verify that the heap is skew
Return node 4
 Analysis
• Height of a skew heap ≈ O(log n)
• Maximum number of values stored in Stack
≈ 2 * O(log n) ≈ O(log n)
• Total cost of merge ≈ O(log n)
 Inserts and Deletes
• To insert a node into a skew heap, merge the
skew heap with the node
• After deleting root X from a skew heap,
merge its left and right subheaps
• In summary, there is only one operation, a
merge.