Lecture 19.
A Priority Queue is a data structure that
supports the operations findMin, deleteMin and insert. Today we saw how to use a
heap to perform the Priority Queue operations. A heap is a binary with special
structural and ordering properties. We saw how to perform the Priority Queue
operations whilst maintaining the heap's structural and ordering properties. I
also showed that these operations could be performed in O( log N) time in the
worst case.
On Wednesday we
will see two different ways to build a heap from scratch. The worst case running
times of these two methods will be O(N log N) and
O(N).
Questions for preparing
for Quiz # 2 have been posted. Please note that Quiz #2 will be held in week of
March 14-18, that is, in week 9.
Posted: Mon - February 28, 2005 at 03:15 PM