Datastruct

Download as pdf or txt
Download as pdf or txt
You are on page 1of 32

Data Structures

20.09.2018

1 / 32
Priority Queues

Many applications require more than just simple data structures.


Consider the problem of scheduling processes in a system.
Each process has a priority.
Processes arrive in arbitrary order of priorities.
Need to maintain a dynamically changing set S of processes.
Ability to add/remove elements from the set: new processes may
arrive, existing ones terminate.
Ability to quickly select the top priority process.
Priority Queue
Add and remove elements in O(log n) time. Find the element with the
smallest key in O(1) time.

2 / 32
Priority Queues

Sorting with Priority Queues


A sequence of O(n) priority queue operations can be used to sort a
set of n numbers.

Add n numbers to a priority queue: n operations each O(log n)


time.
Select and delete n numbers from the priority queue: n
operations each O(log n) time.
Sorting with priority queues is O(n log n).
General purpose sorting is O(n log n).

3 / 32
Priority Queues

Use the heap data structure to implement a priority queue.

Heap Data Structure


The heap is a balanced binary tree. Each node can have at most two
children. The keys are in heap order if a key of an element is as large
or larger as the key at the parent node.

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

Figure: The heap shown as individual nodes, each node containing 3


pointers: left, right and parent.

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

Consider the heap representation as a single block of memory.


We are interested in 3 operations on a heap: add a new element,
delete an existing element and find the element with the smallest
key.
The element with the smallest key is the root of the heap: this
can be found in O(1) time.
Lets assume that the heap H has n < N elements, where N is the
maximum number of elements that can be stored in the array.
Add the new element v at position i = n + 1, by setting H[i] = v.
Now the resulting heap is damaged: the key at node i does not
satisfy the heap property.

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

Heapify-up runs in O(log i) time. Why?


At each step the algorithm divides i by 2 to get the parent node.
How many times can we divide i by 2 to get to 1?

9 / 32
Implementing Heap

Now consider deleting an element from the heap.


Delete element i from a heap H of n elements.
Now there is a hole in the array H, and up to 2 nodes may point
to this hole as their parent.
Move the last element (at position n) to the position i.
Now we have a heap that may be broken because of the key at
position i.
The key at position i may be too small or too big.
If the key is too small: use Heapify-up to fix the heap.
If the key is too big: the heap property may be broken by both of
its children.
Heapify-down: fix the children recursively.

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

Did we fix the heap in Heapify-down?


The key at H[i] is too big compared to its children.
Take the child j having the smallest key.
Swap the element i with j (the keys are swapped also).
The resulting 3 nodes now satisfy the heap property (locally).

13 / 32
Implementing Heap

Now the element at j may break the heap property in relation


with its children.
Use Heapify-down on index j.
At the bottom of the heap (tree), the node has no children.
Here the heap property stands: does not matter how big the key
at the node is.
Using Heapify-up or Heapify-down we can delete an element from
the heap in O(log n) time.

14 / 32
Priority Queues with Heaps

StartHeap(N) initializes an empty heap H that can store up to N


elements. Done once at the start and takes O(N ) time.
Insert(H,v) inserts the item v into heap H, this takes at most
O(log n) time if the heap has n elements.
FindMin(H) returns the element with minimum key from H.
Takes O(1) time.
Delete(H,i) deletes an element at position i from the heap H.
Takes O(log n) time.
ExtractMin(H) Finds and deletes the element with the smallest
key from the heap. This is a combination for FindMin and
ExtractMin and takes O(log n) time.

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.

Binary Search Tree


A Binary Search Tree is an ordered and balanced binary tree.

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

Inserting a new Element


Keys in the tree are unique.
Search for the key of the new element.
If found, overwrite the existing value in the tree, keep the key.
If the key is not found, the search stops at a leaf node.
Depending on the key, add to the leaf node as a left or right child.
Problem: now the tree is not balanced anymore.
Solution: AVL-trees or Red-Black-trees; keep the tree balanced.

20 / 32
AVL trees

AVL-tree: at any node, the difference between depth of the left


and right subsides is at most 1.
At each node keep a balance factor value: how much the
left/right sides are out of balance.
A balance factor of −1, 0, 1 needs no balancing.
At insertion the balance factor of parent nodes must be updated.
Balance factor at a node v:
Balance(v) = Height(vr ) − Height(vl ).

21 / 32
AVL trees

The difference between the heights of the left/right subtrees.


After inserting a new element, the balance factor may be off by 1.
The tree must be rebalanced to keep the AVL tree property.
Only nodes on the path towards the inserted node are out of
balance.
Rebalancing can be done along this path.

22 / 32
Rotations

Left-Rotate(T,x)

x y

α 𝜸
Right-Rotate(T,y)
y x

𝛽 𝜸 α 𝛽

Figure: Rotating a node left or right.

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

Out of balance can be 2 or −2 after one insertion.


25 / 32
Rotations

Left-Rotate(T,x)

x y

α 𝜸
Right-Rotate(T,y)
y x

𝛽 𝜸 α 𝛽

Figure: Left and right rotations used in the next slide.

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

(a) (b) (c)

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

The factor of a node must be updated at insertion.


This can be done at the step of locating the leaf node where the
new element is inserted.
For a node: going left decreases, going right increases the factor.
For example if balance[x] = 1 and the left node is selected, then
set balance[x] = 0.

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

Figure: Deleting a node: keep the tree ordered and balanced.

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

Finding an item in the tree: O(log n) time.


Inserting and deleting: O(log n) time for both.
Provides better balance than red-black trees: better lookup.
Insertion and deletion is slightly slower, but the same asymptotic
time.

32 / 32

You might also like