Datastruct
Datastruct
Datastruct
20.09.2018
1 / 32
Priority Queues
2 / 32
Priority Queues
3 / 32
Priority Queues
Heap Order
For every element v, the element w at v’s parent satisfies
key(w) ≤ key(v).
4 / 32
Heap
2 5
10 3 7 11
15 17 20 9 15 8 16
5 / 32
Heap
1 2 5 10 3 7 11 15 17 20 9 15 8 16 X
Figure: The heap is stored in a single block of memory. The left and right
children of node i are at positions 2i and 2i + 1. The parent of node i is at
position bi/2c
6 / 32
Implementing Heap
7 / 32
Implementing Heap
Problem: when H[i] = v was added to the heap, its value may be
less than its parent.
The rest of the tree should be correct.
Let j be the parent of i and assume that key[H[i]] < key[H[j]],
otherwise all is OK.
Swap the values at i and j in the heap H.
Now i is fixed, but j may be broken: the key at j may be less
than the key at its parent.
Repeat the above swapping on the node j and its parent.
Use the procedure Heapify-up to fix the heap.
8 / 32
Implementing Heap
Heapify-up
Heapify-up(H, i)
if i > 1 then
let j = parent(i) = bi/2c
if key[H[i]] < key[H[j]] then
swap H[i] and H[j]
Heapify-up(H, j)
end
end
9 / 32
Implementing Heap
10 / 32
Implementing Heap
Heapify-down
Heapify-down(H, i)
Let n = length(H)
if 2i > n then
Stop with H
else
if 2i < n then
Let j be the index that minimizes key[H[2i]] and
key[H[2i + 1]]
else
Let j = 2i
end
end
if key[H[j]] < key[H[i]] then
swap the array entries H[i] and H[j].
Heapify-down(H, j).
end
11 / 32
Implementing Heap
The heap was broken at i because the one or two of the children
had two small values.
Heapify-down fixes the heap in O(log n) time.
Why O(log n) time?
At each step, the next index j = 2i and the algorithm stops when
the index is n.
How many times can we multiply an integer by 2 until reaches n?
12 / 32
Implementing Heap
13 / 32
Implementing Heap
14 / 32
Priority Queues with Heaps
15 / 32
Binary Search Trees
Ordered Tree
At any node of a binary search tree, all the keys on the left side are
smaller, and the all keys at the right side are larger than the key at
the node.
Balanced Tree
At any node of the tree, the heights of the left and right subtree differ
by at most 1.
16 / 32
Binary Search Trees
16
8 20
5 11 18 24
2 7 9 14 17 19 22
Figure: Binary Search Tree: at each node the keys follow a strict order.
The tree is balanced.
17 / 32
Binary Search Trees
Finding an Element
Given a key, find the associated element.
At each node compare the search key to the key at the node.
Descend left or right depending on the result.
Depth of a balanced binary tree: 1 + log n.
Number of steps in searching: O(log n).
18 / 32
Finding a Node
FindNode(T,k)
FindNode(T, k)
Let x = root[T ]
while x 6= nil do
if k = key[x] then
return x
else
if k < key[x] then
x = lef t[x];
else
x = right[x];
end
end
end
return nil;
19 / 32
Binary Search Trees
20 / 32
AVL trees
21 / 32
AVL trees
22 / 32
Rotations
Left-Rotate(T,x)
x y
α 𝜸
Right-Rotate(T,y)
y x
𝛽 𝜸 α 𝛽
23 / 32
Rotations
RotateLeft(T,x)
RotateLeft(T, x)
y ← right[x]
right[x] ← lef t[y]
parent[right[y]] ← x
parent[y] ← parent[x]
if parent[x] = nil then
root[T ] ← y
else
if x = lef t[parent[x]] then
lef t[parent[x]] ← y
else
right[parent[x]] ← y
end
end
lef t[y] ← x
parent[x] ← y
24 / 32
Balancing one Node
BalanceNode(T,x)
BalanceNode(T, x)
if balance[x] = -2 then
Let p = lef t[x]
if balance[p] = 1 then
RotateLeft(T, p)
end
RotateRight(T, x)
else
Let p = right[x]
if balance[p] = -1 then
RotateRight(T, p)
end
RotateLeft(T, x)
end
Left-Rotate(T,x)
x y
α 𝜸
Right-Rotate(T,y)
y x
𝛽 𝜸 α 𝛽
26 / 32
Balancing one Node
x x
v
D D
p v
p x
A C
v p A B C D
B C A B
Figure: Balancing one node of the tree after insertion: first rotate p left,
then rotate x right.
27 / 32
Balancing the Tree
BalanceTree(T,x)
BalanceTree(T, x)
while x 6= nil do
if balance[x] ∈ {−2, 2} then
BalanceNode(T,x);
end
x ← parent[x]
end
28 / 32
Inserting a Node
InsertNode(T,y)
InsertNode(T, y)
Let x = root[T ], and p = nil
while x 6= nil do
p = x;
if key[x] = key[y] then
Replace value of x by value of y.
else
if key[y] < key[x] then
x = lef t[x];
else
x = right[x];
end
end
end
if x = nil then
if p 6= nil then
if key[y] < key[p] then
lef t[p] = y
else
right[p] = y
end
BalanceTree(T,y);
else
Set y as the root of T .
end 29 / 32
Deleting a Node
16
8 20
5 11 18 24
2 7 9 14 17 19 22
30 / 32
Deleting a Node
DeleteNode(T,x)
DeleteNode(T, x)
if x is not a leaf node then
Find y = successor(x), or y = predecessor(x).
Replace the content of x by the content of y.
z←y
else
z←x
end
if z has a child node then
Attach it to parent(z), or update root.
end
Let p ← parent(z).
Delete node z.
Update balance factors along the path from p to root.
BalanceTree(T,p);
31 / 32
AVL-Trees
32 / 32