Đang chuẩn bị liên kết để tải về tài liệu:
Lecture Data Structures: Lesson 33

Lecture Data Structures: Lesson 33 provide students with knowledge about priority queue using heap; the selection problem; a faster way is to put the N elements into an array and apply the buildHeap algorithm on this array; disjoint set ADT; . | Priority Queue Using Heap include Event.cpp include Heap.cpp define PQMAX 30 class PriorityQueue public PriorityQueue heap new Heap PQMAX PriorityQueue delete heap Lecture No.33 Data Structure Dr. Sohail Aslam Priority Queue Using Heap Event remove if heap- gt isEmpty Event e heap- gt deleteMin e return e return Event NULL cout Priority Queue Using Heap int insert Event e if heap- gt isFull heap- gt insert e return 1 cout getSize The Selection Problem Given a list of N elements numbers names etc. which can be totally ordered and an integer k find the kth smallest or largest element. One way is to put these N elements in an array an sort it. The kth smallest of these is at the kth position. The Selection Problem A faster way is to put the N elements into an array and apply the buildHeap algorithm on this array. Finally we perform k deleteMin operations. The last element extracted from the heap is our answer. The interesting case is k N 2 since this is known as the median. HeapSort If k N and we record the deleteMin elements as they come off the heap we will have essentially sorted the N elements. Later in the course we will refine this idea to obtain a fast sorting algorithm called heapsort. Disjoint Set ADT Suppose we have a database of people. We want to figure out who is related to whom. Initially we only have a list of people and information about relations is gained by updates of the form Haaris is related to Saad . Disjoint Set ADT Key property If Haaris is related to Saad and Saad is related to Ahmad then Haaris is related to Ahmad. Once we have relationships information we would like to answer queries like Is Haaris related to Ahmad Disjoint Set ADT Blob Coloring A well-known low-level computer vision problem for black and white images is the following Gather together all the picture elements pixels that belong to the same quot blobs quot and give each pixel in each different blob an identical label. Disjoint Set ADT Blob Coloring Thus in the following .