Transcript Algorithm Analysis Neil Tang 01/22/2008

Priority Queue and Binary Heap
Neil Tang
02/09/2010
CS223 Advanced Data Structures and Algorithms
1
Class Overview
 Priority queue
 Binary heap
 Heap operations: insert, deleteMin, de/increaseKey, delete,
buildHeap
 Application
CS223 Advanced Data Structures and Algorithms
2
Priority Queue
A priority queue is a queue in which each element has a
priority and elements with higher priorities are supposed to
be removed before the elements with lower priorities.
CS223 Advanced Data Structures and Algorithms
3
Possible Solutions
 Linked list: Insert at the front (O(1)) and traverse the list
to delete (O(N)).
 Linked list: Keep it always sorted. traverse the list to
insert (O(N)) and delete the first element (O(1)).
 Binary search tree
CS223 Advanced Data Structures and Algorithms
4
Binary Heap
A binary heap is a binary tree that is completely filled, with possible
exception of the bottom level and in which for every node X, the key in
the parent of X is smaller than (or equal to) the key in X.
CS223 Advanced Data Structures and Algorithms
5
Binary Heap
 A complete binary tree of height h has between 2h and
2h+1 -1 nodes. So h = logN.
 For any element in array position i, its left child in position
2i and the right child is in position (2i+1), and the parent
is in i/2.
CS223 Advanced Data Structures and Algorithms
6
Insert 14
CS223 Advanced Data Structures and Algorithms
7
Insert (Percolate Up)
Time complexity: O(logN)
CS223 Advanced Data Structures and Algorithms
8
deleteMin
CS223 Advanced Data Structures and Algorithms
9
deleteMin
(Percolate Down)
Time complexity: O(logN)
CS223 Advanced Data Structures and Algorithms
10
Other Operations
 decreaseKey(p,)
 increaseKey(p, )
 delete(p)?
 delete(p)=decreaseKey(p,)+deleteMin()
CS223 Advanced Data Structures and Algorithms
11
buildHeap
CS223 Advanced Data Structures and Algorithms
12
buildHeap
CS223 Advanced Data Structures and Algorithms
13
buildHeap
CS223 Advanced Data Structures and Algorithms
14
buildHeap
 Theorem: For the perfect binary tree of height h with (2h+11) nodes the sum of the heights of the nodes is (2h+1-1(h+1)).
 Time complexity: 2h+1-1-(h+1) = O(N).
CS223 Advanced Data Structures and Algorithms
15
Applications
 Problem: find the kth smallest element.
 Algorithm: buildHeap, then deleteMin k times.
 Time complexity: O(N+klogN) = O(NlogN).
CS223 Advanced Data Structures and Algorithms
16
Applications
 Problem: find the kth largest element.
 Algorithm: buildHeap with the first k elements, check the
rest one by one. In each step, if the new element is larger
than the element in the root node, deleteMin and insert
the new one.
 Time complexity: O(k+(N-k)logk) = O(NlogN).
CS223 Advanced Data Structures and Algorithms
17