CSE201-DATA STRUCTURES

Heaps-II

1
CONTENT

 Heap-sort
 Leftist Heaps
 Binomial Heaps

2
HEAP-SORT

3
 HEAPSORT

• Idea: Delete_Min operation in a minimum heap

removes the key in root.
• The hole at the root percolates down where, in
the array we keep the minimum heap, proper
keys are moved left accordingly.
• The last cell in the array becomes available
for storing another key.
• If we perform the delete_min operation n times
in an n-element min heap and place the ithkey
removed at the available cell A[n-i], we will obtain
a sorted sequence of the keys in the heap in
descending order.
21.Aralık.2010 Borahan Tümer, Ph.D. 4
ALGORITHM OF HEAPSORT

int heapsort(Elmnt_Type *A)

{ // sorts keys in minheap A in descending
order...
Elmnt_Type x;
for (i=1;i<=n;i++)
{
x=DeleteMin(A); // O(lgn)
A[n-i]=x; // O(1)
}
}
21.Aralık.2010 Borahan Tümer, Ph.D. 5
HEAP-SORT
8

15 21

46 37 27 23

92 93 45 116 42 87 34 66

111 98 95

Empty 8 15 21 46 37 27 23 92 93 45 116 42 87 34 66 111 98 95

6
HEAP-SORT
8

15 21

46 37 27 23

92 93 45 116 42 87 34 66

111 98 95

Empty 8 15 21 46 37 27 23 92 93 45 116 42 87 34 66 111 98 95

7
HEAP-SORT
15

37 21

46 45 27 23

92 93 95 116 42 87 34 66

111 98

Empty 15 37 21 46 45 27 23 92 93 95 116 42 87 34 66 111 98 8

 HEAP-SORT
21

37 23

46 45 27 34

92 93 95 116 42 87 98 66

111

Empty 21 37 23 46 45 27 34 92 93 95 116 42 87 98 66 111 15 8

HEAP-SORT

23

37 27

46 45 42 34

92 93 95 116 111 87 98 66

Empty 23 37 27 46 45 42 34 92 93 95 116 111 87 98 66 21 15 8

HEAP-SORT

27

37 34

46 45 42 66

92 93 95 116 111 87 98

Empty 27 37 34 46 45 42 66 92 93 95 116 111 87 98 23 21 15 8

HEAP-SORT

34

37 42

46 45 87 66

92 93 95 116 111 98

Empty 34 37 42 46 45 87 66 92 93 95 116 111 98 27 23 21 15 8

HEAP-SORT

37

45 42

46 95 87 66

92 93 98 116 111

Empty 37 45 42 46 95 87 66 92 93 98 116 111 34 27 23 21 15 8

 HEAP-SORT

42

45 66

46 95 87 111

92 93 98 116

Empty 42 45 66 46 95 87 111 92 93 98 116 37 34 27 23 21 15 8

 HEAP-SORT

45

46 66

92 95 87 111

116 93 98

Empty 45 46 66 92 95 87 111 116 93 98 42 37 34 27 23 21 15 8

 HEAP-SORT

46

92 66

93 95 87 111

116 98

Empty 46 92 66 93 95 87 111 116 98 45 42 37 34 27 23 21 15 8

 HEAP-SORT

66

92 87

93 95 98 111

116

Empty 66 92 87 93 95 98 111 116 46 45 42 37 34 27 23 21 15 8

 HEAP-SORT

87

92 98

93 95 116 111

Empty 87 92 98 93 95 116 111 66 46 45 42 37 34 27 23 21 15 8

HEAP-SORT

92

93 98

111 95 116

Empty 92 93 98 111 95 116 87 66 46 45 42 37 34 27 23 21 15 8

HEAP-SORT

93

95 98

111 116

Empty 93 95 98 111 116 92 87 66 46 45 42 37 34 27 23 21 15 8

HEAP-SORT

95

111 98

116

Empty 95 111 98 116 93 92 87 66 46 45 42 37 34 27 23 21 15 8

HEAP-SORT

98

111 116

Empty 98 111 116 95 93 92 87 66 46 45 42 37 34 27 23 21 15 8

HEAP-SORT

111

116

Empty 111 116 98 95 93 92 87 66 46 45 42 37 34 27 23 21 15 8

 HEAP-SORT

116

Empty 116 111 98 95 93 92 87 66 46 45 42 37 34 27 23 21 15 8

Sequence in the array is sorted in

descending order!
Empty 116 111 98 95 93 92 87 66 46 45 42 37 34 27 23 21 15 8
ALGORITHM ANALYSIS OF HEAP SORT

• Every turn of the for loop:

– One delete_min is performed, O(lg n);
– Key in the root is placed in last element of the current
queue, O(1).
• For loop is executed n times for a heap with n
elements
• Hence, running time of heap sort is O(n lgn).

21.Aralık.2010 Borahan Tümer, Ph.D. 25

LEFTIST HEAPS

26
MOTIVATION FOR LEFTIST HEAPS

 Leftist heaps make merging possible in O(log n) time

(log n insertions each with O(1) average time) using only
an array as in binary heaps.
 LHs have both
 a structural property, and
 an ordering property.
 A LH has the same heap order property.
 A LH is a binary tree.
 Difference between a LH and a binary heap is
 a LH is not perfectly balanced.

27
LEFTIST HEAP PROPERTY

 Definition:
 Null path length of a node X, Npl(X), is defined as the length
of the shortest path from X to a node without two children.
 By definition, Npl(NULL)=-1.
 Npl(leaf)=0.
 LH property is that for every node X in the heap,
 Npl(LCX)  Npl(RCX)
 where LCX and RCX denote the left child and the right child
of node X, respectively.

28
29
LEFTIST
Example 1: Consider the heap below is it leftist?

30
LEFTIST
Example 2: Consider the heaps below are they leftist?

1 7 4 1

1 8 16 0 1 11 19 0

0 21 0 12 0 17 46
0 25 0

31
LEFTIST HEAPS / TREES

Merging mechanisms of leftist trees:

- Recursive Merging
- Non-Recursive Merging

32
LEFTIST- RECURSIVE MERGING
Example 3: Recursively merge the two leftist heaps showing each immediate step.

7 Compare 4

8 16 11 19

21 12 17 46 25

33
 4

11 19 Compare 7

17 46 25 8 16

21 12

34
 4

11
7

17 46 8 Compare
16 19

21 12 25

35
 4

11
7

17 46 8 16

21 12 19

25

36
LEFTIST - RECURSIVE MERGING
Example 4: Recursively merge the two leftist heaps showing each immediate step.

37
38
39
40
LEFTIST – NONRECURSIVE MERGING
Example 5: Non recursively merge the two leftist heaps showing each immediate
step.

41
NON RECURSIVE MERGING ALGORITHM

Requires 2 passes on the heap:

First pass: Create a new tree by merging

the right paths of both heaps in sorted order
Second pass: Perform child swaps at
nodes that violate the leftist heap property.

42
3 8 6 7 18  SORT  3 6 7 8 18

43
 Heaps

First pass

44
First pass

Second pass

45
BINOMIAL HEAPS

46
MOTIVATION FOR BINOMIAL HEAPS

 A Binomial Heap is a set of Binomial Trees,

 where each Binomial Tree follows the Min Heap
property.
 And there can be at most one Binomial Tree of any
degree.

47
MOTIVATION FOR BINOMIAL HEAPS

 Leftist Heaps support

 merging, insertion, removal, and deleteMin
 in O(log(n)) time per operation.
 We know binary heaps have a constant (i.e., O(1))
insertion time.
 Question: May there be a data structure providing
 O(1) time for insertion, and
 O(log(n)) time for each other operation.
 This data structure is the so-called binomial heaps (BHs)
or binomial queues.
 To study BHs we first need to discuss binomial trees.

48
BINOMIAL TREES

 A binomial tree Bk is an ordered tree (i.e., a

rooted tree in which the children of each node are
ordered; the order of the children matters) defined
recursively.
 The binomial tree B0 consists of a single node. A
binomial tree Bk of height k is formed by
attaching a Bk-1 to the root of another Bk-1.
 In the next slide, we see two B3s combined to
form a B4.

49
BINOMIAL TREES
Useful properties of order k binomial tree Bk.
• Number of nodes = 2𝑘 .
• Height = k.
• Degree of root = k.
• Deleting root yields binomial trees B k-1 , … , B0.

The binomial trees B0 through B4. Node depths in B4 are shown. below

50
51
BINOMIAL TREES

 A binomial tree Bk has

a height of k;
 n = 2k nodes (!!!);

 k+1 depth levels ranging within 0,...,k.

k  k!
    nodes at depth level d.
d  d! (k  d )!
a root and a B0, B1, B2, B3,..., Bk-1 connected to
it in respective order (see slide 96!).

52
BINOMIAL HEAPS

 BHs differ from other heap structures in that

 a BH is not a heap-ordered tree but rather a collection of heap
ordered trees, a forest.
 each heap-ordered tree is of a constrained form known as a
binomial tree.
 Each binomial tree in a BH obeys min-heap or heap
order property.
 There is at most one Bk of each height k in a BH.
 In the next slide, we see an 11-node BH.

53
BINOMIAL HEAPS
Example 6: What is the Node number, tree number, height and the binary equivalent
of the following tree.

54
55
Example 7: Merge the following binomial trees and show the result.

56
57
Example 8: Merge the following binomial heaps and show the result step by step.

58
59
Example 9: Delete the node with minimum key in binomial heap H and show the
result.

60
H ← Union(H’, H)

61
Example 10: If x=11 insert x into the following heap and show the result.

62
Example 11: How many binomial trees are there in a binomial heap with n element,
while n>0?
a. At least
b. At most

63
Example 11: How many binomial trees are there in a binomial heap with n element,
while n>0?
a. At least
b. At most

64
Example 11: How many binomial trees are there in a binomial heap with n element,
while n>0?

Answer:
a. At least: 1  if n is 1
b. At most:  log 2 (𝑛 + 1)

65
Example 12: How many binomial trees are there in a binomial heap with n element?
If n is equal to 4378

66
Example 12: How many binomial trees are there in a binomial heap with n element?
If n is equal to 4378

4378=4096 + 256 + 16 + 8 + 2

4378=212 + 28 + 24 + 23 + 21

4378= 𝐵12 + 𝐵8 + 𝐵4 + 𝐵3 + 𝐵1

67
Example 13: How many leaves does a binomial tree with n elements have?

68
Example 13: How many leaves does a binomial tree with n elements have?

Answer: n/2

69
Example 14: Where and how many nodes would you search to find the max key in a
binomial tree Bi confirming to the min-heap order property?

70
Example 14: Where and how many nodes would you search to find the max key in a
binomial tree Bi confirming to the min-heap order property?

Answer: n/2 because in a min-heap maximum element is in one of the leafs.

71
REFERENCES
https://courses.cs.washington.edu/courses/cse326/00wi/handouts/lecture7/sld018.htm
http://www.cs.princeton.edu/~wayne/cs423/lectures/heaps-4up.pdf
T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, “Introduction to Algorithms,” 2nd
edition, MIT Press, 2003

72