Advanced Data Structures

23CS6PEADS – Unit 5
Prof. SNEHA S BAGALKOT
Assistant Professor, Dept. of CSE, BMSCE
 UNIT – 5: Heaps
▪Priority Queues: Model, Simple implementation,
▪Binary Heap: structure property, heap-order property, other operations,
▪d-heaps,
▪Leftist heaps: property, operations,
▪Skew heaps.
▪Advanced Hashing: Perfect Hashing, Cuckoo Hashing,
▪Hopscotch Hashing, Universal Hashing.
Priority Queues (Heaps)
 Motivation
■ Queues are a standard mechanism for ordering tasks on a
first-come, first-served basis
■ However, some tasks may be more important or timely
than others (higher priority)
■ Priority queues
■ Store tasks using a partial ordering based on priority
■ Ensure highest priority task at head of queue
■ Heaps are the underlying data structure of priority queues
 Priority Queues: Specification
■ Main operations
■ insert (i.e., enqueue)
■ Dynamic insert
■ specification of a priority level (0-high, 1,2.. Low)
■ deleteMin (i.e., dequeue)
■ Finds the current minimum element (read: “highest priority”) in the
queue, deletes it from the queue, and returns it

■ Performance goal is for operations to be “fast”

Using priority queues
4
10
19
3
5
13 8
1 22
1
insert()

deleteMin()
Dequeues the next element
2
with the highest priority
Can we build a data structure better suited to store and retrieve priorities?

Simple Implementations
■ Unordered linked list 5 2 10 … 3

■ O(1) insert
■ O(n) deleteMin
… 10
■ Ordered linked list 2 3 5

■ O(n) insert
■ O(1) deleteMin
2 3 5 … 10
■ Ordered array
■ O(lg n + n) insert
■ O(n) deleteMin
■ Balanced BST
■ O(log2n) insert and deleteMin
Binary Heap
A priority queue data structure
Binary Heap

■ A binary heap is a binary tree with two

properties
■ Structure property
■ Heap-order property
Structure Property

■ A binary heap is a complete binary tree

■ Each level (except possibly the bottom most level)
is completely filled
■ The bottom most level may be partially filled
(from left to right)

■ Height of a complete binary tree with N

elements is log2 N
 
 Structure property

Binary Heap Example

N=10

Every level
(except last)
saturated

Array representation:
 Heap-order Property
■ Heap-order property (for a “MinHeap”)
■ For every node X, key(parent(X)) ≤ key(X)

■ Except root node, which has no parent

 Thus minimum key always at root
■ Alternatively, for a “MaxHeap”, always keep the
maximum key at the root

■ Insert and deleteMin must maintain

heap-order property
Heap Order Property
Minimum
  element

   

   

■ Duplicates are allowed

■ No order implied for elements which do not
share ancestor-descendant relationship
Implementing Complete Binary Trees as Arrays

■ Given element at position i in the array

■ Left child(i) = at position 2i
■ Right child(i) = at position 2i + 1
■ Parent(i) = at position i /

2

i
2i
2i + 1
i/2
 Just finds the Min
without deleting it
insert
deleteMin

Note: a general delete()

function is not as important
Stores the heap as for heaps
a vector but could be implemented

Fix heap after

deleteMin
Heap Insert

■ Insert new element into the heap at the

next available slot (“hole”)
■ According to maintaining a complete binary
tree
■ Then, “percolate” the element up the
heap while heap-order property not
satisfied
 Percolating Up

Heap Insert: Example

Insert 14:

hole
14
 Percolating Up

Heap Insert: Example

(1)
Insert 14: 14 vs. 31

14

hole
14
 Percolating Up

Heap Insert: Example

(1)
Insert 14: 14 vs. 31

14

hole
14
(2)
14 vs. 21

14
 Percolating Up

Heap Insert: Example

(1)
Insert 14: 14 vs. 31

hole
14
(2)
14 vs. 21
Heap order prop
14 (3)
14 vs. 13 Structure prop

Path of percolation up
Heap Insert: Implementation
// assume array implementation
void insert( const Comparable &x) {
?
}
Heap Insert: Implementation

O(log N) time
Heap DeleteMin

■ Minimum element is always at the root

■ Heap decreases by one in size
■ Move last element into hole at root
■ Percolate down while
heap-order property not satisfied
 Percolating down…

Heap DeleteMin:
Example

Make this
position
empty
 Percolating down…

Heap DeleteMin: Example

Copy 31 temporarily
here and move it down

Make this
position Is 31 > min(14,16)?
•Yes - swap 31 with min(14,16)
empty
 Percolating down…

Heap DeleteMin:
Example

31

Is 31 > min(19,21)?
•Yes - swap 31 with min(19,21)
 Percolating down…

Heap DeleteMin: Example

31

31

Is 31 > min(19,21)? Is 31 > min(65,26)?

•Yes - swap 31 with min(19,21) •Yes - swap 31 with min(65,26)

Percolating down…
 Percolating down…

Heap DeleteMin: Example

31

Percolating down…
 Percolating down…

Heap DeleteMin: Example

31

Heap order prop

Structure prop
Heap DeleteMin: Implementation

O(log N) time
Heap DeleteMin: Implementation

Percolate
down

Left child

Right child

Pick child to
swap with
Other Heap Operations
■ decreaseKey(p,v)
■ Lowers the current value of item p to new priority value v
■ Need to percolate up
■ E.g., promote a job
■ increaseKey(p,v)
■ Increases the current value of item p to new priority value v
■ Need to percolate down
■ remove(p)
■ E.g., demote a job Run-times for all three functions?
■ First, decreaseKey(p,-∞)
O(lg n)
■ Then, deleteMin
■ E.g., abort/cancel a job
Improving Heap Insert Time
■ What if all N elements are all available
upfront?

■ To build a heap with N elements:

■ Default method takes O(N lg N) time
■ We will now see a new method called buildHeap()
that will take O(N) time - i.e., optimal
Building a Heap
■ Construct heap from initial set of N items
■ Solution 1
■ Perform N inserts
■ O(N log2 N) worst-case
■ Solution 2 (use buildHeap())
■ Randomly populate initial heap with structure
property
■ Perform a percolate-down from each internal node
(H[size/2] to H[1])
■ To take care of heap order property
 BuildHeap Example
Input: { 150, 80, 40, 10, 70, 110, 30, 120, 140, 60, 50, 130, 100, 20, 90 }

Leaves are all

valid heaps
(implicitly)

So, let us look at each

•Arbitrarily assign elements to heap nodes internal node,
• Structure property satisfied from bottom to top,
• Heap order property violated and fix if necessary
• Leaves are all valid heaps (implicit)
BuildHeap Example
Swap
with left
Nothing child
to do

• Randomly initialized heap

• Structure property satisfied
• Heap order property violated
• Leaves are all valid heaps
BuildHeap Example Swap
with right
Nothing child
to do

Dotted lines show path of percolating down

 Swap with
right child
BuildHeap Example & then with 60

Nothing
to do

Dotted lines show path of percolating down

BuildHeap Example

Swap path

Final Heap

Dotted lines show path of percolating down

BuildHeap Implementation

Start with
lowest,
rightmost
internal node
BuildHeap() : Run-time Analysis
■ Run-time = ?
■ O(sum of the heights of all the internal nodes)
because we may have to percolate all the way
down to fix every internal node in the worst-case
■ Theorem 6.1 HOW?

■ For a perfect binary tree of height h, the sum

of heights of all nodes is 2h+1 – 1 – (h + 1)
■ Since h=lg N, then sum of heights is O(N)
■ Will be slightly better in practice

Implication: Each insertion costs O(1) amortized

time
Binary Heap Operations
Worst-case Analysis
Height of heap is log2 N
 
■

■ insert: O(lg N) for each insert

■ In practice, expect less
■ buildHeap insert: O(N) for N inserts
■ deleteMin: O(lg N)
■ decreaseKey: O(lg N)
■ increaseKey: O(lg N)
■ remove: O(lg N)
Applications

■ Operating system scheduling

■ Process jobs by priority
■ Graph algorithms
■ Find shortest path
■ Event simulation
■ Instead of checking for events at each time
click, look up next event to happen
An Application:
The Selection Problem

■ Given a list of n elements, find the kth

smallest element

■ Algorithm 1:
■ Sort the list =>O(n log n)
■ Pick the kth element => O(1)
■ A better algorithm:
■ Use a binary heap (minheap)
Selection using a MinHeap

 Input: n elements
 Algorithm:
1. buildHeap(n) ==> O(n)
2. Perform k deleteMin() operations ==> O(k log
n)
3. Report the kth deleteMin output ==> O(1)
Total run-time = O(n + k log n)

If k = O(n/log n) then the run-time becomes O(n)

Other Types of Heaps
■ Binomial Heaps

■ d-Heaps
■ Generalization of binary heaps (ie., 2-Heaps)

■ Leftist Heaps
■ Supports merging of two heaps in o(m+n) time (ie., sub-
linear)
■ Skew Heaps
■ O(log n) amortized run-time

■ Fibonacci Heaps
Run-time Per Operation

Insert DeleteMin Merge (=H1+H2)

Binary heap ■ O(log n) worst-case O(log n) O(n)

■ O(1) amortized
for buildHeap
Leftist Heap O(log n) O(log n) O(log n)

Skew Heap O(log n) O(log n) O(log n)

Binomial ■ O(log n) worst case O(log n) O(log n)

Heap ■ O(1) amortized
for sequence of n
inserts
Fibonacci Heap O(1) O(log n) O(1)
Priority Queues in STL
■ Uses Binary
#include
heap <priority_queue> int
main ()
{
■
■ Default
Methodsis MaxHeap priority_queue<int>
Q; Q.push (10);
■ Push, top, pop, cout << Q.top
empty, clear (); Q.pop ();
}
Calls DeleteMax()

For MinHeap: declare priority_queue as:

priority_queue<int, vector<int>, greater<int>> Q;
Summary

■ Priority queues maintain the minimum

or maximum element of a set
■ Support O(log N) operations worst-case
■ insert, deleteMin, merge
■ Many applications in support of other
algorithms
 Facts about Heaps
Observations:
• Finding a child/parent index is a multiply/divide by two

• Operations jump widely through the heap

• Each percolate step looks at only two new nodes

• Inserts are at least as common as deleteMins

Realities:
• Division/multiplication by powers of two are equally fast

• Looking at only two new pieces of data: bad for cache!

• With huge data sets, disk accesses dominate

 Cycles to access:

CPU

Cache

Memory

Disk
 A Solution: d-Heaps
• Each node has d children
• Still representable by array 1
• Good choices for d:
• (choose a power of two for 3 7 2
efficiency)
• fit one set of children in a 1 1 1
4 8 5 6 9
cache line 2 1 0
• fit one set of children on a 1 1 1 1
1 3 7 2 4 8 5 6 9
memory page/disk block 2 2 1 0
One More Operation
• Merge two heaps

• Add the items from one into another?

• O(n log n)

• Start over and build it from scratch?

• O(n)
Leftist Heaps
• Review of Min Heaps
• Introduction of Left-ist Heaps
• Merge Operation
• Heap Operations
Review of Heaps
 Min Binary Heap
• A min binary heap is a…
– Complete binary tree
– Neither child is smaller than the value in the parent
– Both children are at least
as large as the parent
• In other words,
smaller items go
above larger ones
 Min Binary Heap Performance

• Performance
– (n is the number of elements in the heap)

• construction O( n )
• findMin() O( 1 )
• insert() O( lg n )
• deleteMin() O( lg n )
 Problem
• Suppose you’re using more than one heap
– Multiple emergency rooms, etc.
• What if you need to merge them?
– One is too small, etc.
• Merging regular heaps is O(m+n)
Introduction to Leftist
Heaps
Leftist Heaps
Idea:
Focus all heap maintenance work in one small part of the heap

Leftist heaps:
1. Most nodes are on the left
2. All the merging work is done on the right
 Definition: Null Path Length
null path length (npl) of a node x = the number of nodes between x
and a null in its subtree
OR
npl(x) = min distance to a descendant with 0 or 1 children

• npl(null) = -1 ?
• npl(leaf) = 0
• npl(single-child node) = 0 ? ?

Equivalent definitions: 0 1 ? 0

1. npl(x) is the height of largest

complete subtree rooted at x 0 0 0
2. npl(x) = 1 + min{npl(left(x)), npl(right(x))}
62
 Leftist Heap Properties
• Heap-order property
• parent’s priority value is ≤ to childrens’ priority values
• result: minimum element is at the root

• Leftist property
• For every node x, npl(left(x)) ≥ npl(right(x))
• result: tree is at least as “heavy” on the left as the right
Are These Leftist?

2 2 0

1 1 1 1 0

0 1 0 0 1 0 0 0 1

0 0 0 0 0 0 0 0

0
Every subtree of a leftist
0
tree is leftist!
0
64
 Leftist Heap Concepts
• Structurally, a leftist heap is a min tree where each
node is marked with a rank value.
• Uses a Binary Tree (BT)
• Merging heaps is much easier and faster
– May use already established links to merge with a new
node
– Rather than copying pieces of an array
 Leftist Heap Concepts
• Values STILL obey a heap order (partial order)
• Uses a null path length to maintain the structure
(covered in detail later)
– The null path of a node’s left child is >=
null path of the right child
• At every node, the shortest path to a non-full node is
along the rightmost path
 Leftist Heap Example
• A leftist heap, then, is a
purposefully unbalanced 2
binary tree (leaning to the
left, hence the name) that 3 7
keeps its smallest value at
9 8 10 15
the top and has an
inexpensive merge 8
operation
 Leftist Heap Performance

• Leftist Heaps support:

– findMin() = O(1)
– deleteMin() = O(log n)
– insert() = O(log n)
– construct = O(n)
– merge() = O(log n)
 Null Path Length (npl)
• Length of shortest path from current node to a node
without exactly 2 children
– value is stored IN the node itself
• leafs
– npl = 0
• nodes with only 1 child
– npl = 0
Null Path Length (npl) Calculation
To calculate the npl for each node,
we look to see how many nodes
we need to traverse to get to an
2 open node

3 7
9 8 10 15
8
Null Path Length (npl) Calculation
Leaves -> npl = 0
One
2 child -> npl = 0
Others -> npl = 1 + min(left, right)
2

2
1 1

3 7
0 0 0 0

9 8 10 15
0

8
 Leftist Node
• The leftist heap node should keep track of:
– links (left and right)
– element (data)
– npl
 Leftist Node Code
Looks like a binary
private:
struct LeftistNode tree node except the
{
Comparable element;
npl being stored.
LeftistNode *left;
LeftistNode *right;
int npl;

LeftistNode( const Comparable & theElement, LeftistNode *lt = NULL,

LeftistNode *rt = NULL, int np = 0 )
: element( theElement ), left( lt ), right( rt ), npl( np ) { }
};

LeftistNode *root;
Building a Leftist Heap
 Building a Leftist Heap
• Value of node STILL matters
– Lowest value will be root, so still a min Heap
• Data entered is random

• Uses CURRENT npl of a node to determine where the

next node will be placed
 Leftist Heap Algorithm
• Add new node to right-side of tree, in order
• If new node is to be inserted as a parent (parent < children)
– make new node parent
– link children to it
– link grandparent down to new node (now new parent)
• If leaf, attach to right of parent
• If no left sibling, push to left (hence left-ist)
– why?? (answer in a second)
• Else left node is present, leave at right child
• Update all ancestors’ npls
• Check each time that all nodes left npl > right npls
– if not, swap children or node where this condition exists
Merging Leftist Heaps
 Merging Leftist Heaps
• In the code, adding a single node is treated as
merging a heap (just one node) with an established
heap’s root
– And work from that root as we just went over
 Merging Leftist Heaps
• The heaps we are about to merge must be LEFTIST
heaps
• At the end we will get a heap that is both
– a min-heap
– leftist
 Merging Leftist Heaps
• The Merge procedure takes two leftist trees, A and B,
and returns a leftist tree that contains the union of
the elements of A and B. In a program, a leftist tree is
represented by a pointer to its root.
 Merging Leftist Heaps Example
2
1 0
1 1
5 22
7 0
0 0 1 0
75
10 15 20 25
0 0

50 99

Where should we
attempt to merge?
 Merging Leftist Heaps Example

7 22

75
20 25

50 99

In the right sub-tree

 Merging Leftist Heaps Example

22

75
25

All the way down to

the right most node
 Merging Leftist Heaps Example

22
75 25

Important: We don’t “split”

As there are two a heap, so 22 must be
nodes in the right the parent in this merge
subtree, swap.
 Merging Leftist Heaps Example

22

75 25

Merge two subtrees

 Merging Leftist Heaps Example

20 22
50 99 75 25

Next level of the tree

 Merging Leftist Heaps Example
1
1 2

5 7

10 15 20 22

50 99 75 25

Right side of the tree

has a npl of 2 so we
need to swap
 Merging Leftist Heaps Example
2
1
2 1

7 5

20 22 10 15
50 99 75 25

Now the highest npl

is on the left.
 Merging Leftist Heaps
– Compare the roots. Smaller root becomes new root of
subheap
– “Hang up” the left child of the new root
– Recursively merge the right subheap of the new root with
the other heap.
– Update the npl
– Verify a leftist heap! (left npl >= right npl)
• if not, swap troubled node with sibling
 Merging Leftist Heaps Code
/**
* Merge rhs into the priority queue.
* rhs becomes empty. rhs must be different from this.
*/
void merge( LeftistHeap & rhs )
{
if( this == &rhs ) // Avoid aliasing problems
return;

root = merge( root, rhs.root );

rhs.root = NULL;
}
 Merging Leftist Heaps Code
/**
* Internal method to merge two roots.
* Deals with deviant cases and calls recursive merge1.
*/
LeftistNode * merge( LeftistNode *h1, LeftistNode *h2 )
{
if( h1 == NULL )
return h2;
if( h2 == NULL )
return h1;
if( h1->element < h2->element )
return merge1( h1, h2 );
else
return merge1( h2, h1 );
}
 Merging Leftist Heaps Code
/**
* Internal method to merge two roots.
* Assumes trees are not empty, & h1's root contains smallest item.
*/
LeftistNode * merge1( LeftistNode *h1, LeftistNode *h2 )
{
if( h1->left == NULL ) // Single node
h1->left = h2; // Other fields in h1 already accurate
else
{
h1->right = merge( h1->right, h2 );
if( h1->left->npl < h1->right->npl )
swapChildren( h1 );
h1->npl = h1->right->npl + 1;
}
return h1;
}
Deleting from Leftist
Heap
 Deleting from Leftist Heap
• Simple to just remove a node (since at top)
– this will make two trees
• Merge the two trees like we just did
 Deleting from Leftist Heap
We remove the root.
2
1
3
1

8 10
0 0 0 0

14 23 21 17
0

26
 Deleting from Leftist Heap
Then we do a merge
2
and because min is in
1
3 left subtree, we
1

8 recursively merge
10
0 0 0 0 right into left
14 23 21 17
0

26
 Deleting from Leftist Heap
Then we do a merge
2
and because min is in
3 left subtree, we
1 1

8 recursively merge
10
0 0 0 0 right into left
14 23 21 17
0

26
 Deleting from Leftist Heap
1
After Merge
8
1 0

10 14
1 0

17 26
0 0

21 23
 Leftist Heaps
• Merge with two trees of size n
– O(log n), we are not creating a totally new tree!!
– some was used as the LEFT side!
• Inserting into a left-ist heap
– O(log n)
– same as before with a regular heap
• deleteMin with heap size n
– O(log n)
– remove and return root (minimum value)
– merge left and right subtrees
 Skew Heaps
Problems with leftist heaps
• extra storage for npl
• extra complexity/logic to maintain and check npl
• right side is “often” heavy and requires a switch
Solution: skew heaps
• “blindly” adjusting version of leftist heaps
• merge always switches children when fixing right path
• amortized time for: merge, insert, deleteMin = O(log n)
• however, worst case time for all three = O(n)
 Merging Two Skew Heaps
merge
T1
a a
merge
L R R L
a<b
1 1 1
1
T2 b b

L R L R
2 2 2 2

Only one step per iteration, with children always switched

 Example
merge
5 3 3
merge
1 1 7 5 7
0 2 5
1 merge 1 1
1 1 1
3 4 0 4
0 2 2
8
7 8 8
3
1
4
5 7
1 1
8
0 4
1
2
Skew Heap Code
void merge(heap1, heap2) {
case {
heap1 == NULL: return heap2;
heap2 == NULL: return heap1;
heap1.findMin() < heap2.findMin():
temp = heap1.right;
heap1.right = heap1.left;
heap1.left = merge(heap2, temp);
return heap1;
otherwise:
return merge(heap2, heap1);
}
}
 Runtime Analysis:
Worst-case and Amortized
• No worst case guarantee on right path length!
• All operations rely on merge

⇒ worst case complexity of all ops =

• Probably won’t get to amortized analysis in this
course, but see Chapter 11 if curious.
• Result: M merges take time M log n

⇒ amortized complexity of all ops =

Comparing Heaps
• Binary Heaps • Leftist Heaps

• d-Heaps • Skew Heaps

THANK
YOU