### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# DATA STRUCTURES CS 261

OSU

GPA 3.95

### View Full Document

## 16

## 0

## Popular in Course

## Popular in ComputerScienence

This 14 page Class Notes was uploaded by Mrs. Maximo Lueilwitz on Monday October 19, 2015. The Class Notes belongs to CS 261 at Oregon State University taught by R. Metoyer in Fall. Since its upload, it has received 16 views. For similar materials see /class/224497/cs-261-oregon-state-university in ComputerScienence at Oregon State University.

## Reviews for DATA STRUCTURES

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 10/19/15

Chapter 11 Priority Queues and Heaps In this chapter we examine yet another variation on the simple Bag data structure A priority queue maintains values in order of importance A metaphor for a priority queue is a todo list of tasks waiting to be performed or a list of patients waiting for an To Do operating room in a hospital The key feature is that you want to be able to quickly nd the most important item the value with 1 urgent highest priority 2needed Like a bag you can add new elements into the priority queue 303 wait However the only element that can be accessed or removed is the one value with highest priority In this sense the container is like the stack or queue where it was only the element at the top or the front of the collection that could be removed The Priority Queue ADT speci cation The traditional definition of the Priority Queue abstraction includes the following operations Normally priority is defined by the user who provides a comparison function that can be applied to any two elements The element with the largest or sometimes the smallest value will the deemed the element with highest priority A priority queue is not in the technical sense a true queue as described in Chapter 7 To be a queue elements would need to satisfy the FIFO property This is clearly not the case for the priority queue However the name is now firmly attached to this abstraction so it is unlikely to change The following table shows priority queue operation names in the C STL and in the Java class PriorityQueue C S TL Java or test Chapter 11 Priority queues and Heaps l In C it is the element with the largest value as de ned by the user provided comparison function that is deemed to be the first value In the Java library on the other hand it is the element with the smallest value However since the user provides the comparison function it is easy to invert the sense of any test We will use the smallest value as our first element Applications of Priority Queues The most common use of priority queues is in simulation A simulation of a hospital waiting room for example might prioritize patients waiting based on the severity of their need A common form of simulation is termed a discrete eventdriven simulation In this application the simulation proceeds by a series of events An event is simply a representation of an action that occurs at a given time The priority queue maintains a collection of events and the event with highest priority will be the event with lowest time that is the event that will occur next For example suppose that you are simulating patrons arriving at a small resturant There are three main types of event of interest to the simulation namely patrons arriving the arrival event patrons ordering the order event and patrons leaving the leave event An event might be represented by a structure such as the following struct eventStruot int time int groupsize enum arriva order leave eventType To initialize the simulation you randomly generate a number of arrival events for groups of various sizes and place them into the queue The execution of the simulation is then described by the following loop while the event queue is not empty select and remove the next event do the event which may generate new events To do the event means to act as if the event has occurred For example to do an arrival event the patrons walk into the resturant If there is a free table they are seated and an subsequent order event is added to the queue Otherwise if there is not a free table the patrons either leave or remain in a queue of waiting patrons An order event produces a subsequent leave event When a leave event occurs the newly emptied table is then occupied by any patrons waiting for a table otherwise it remains empty until the next arrival event Many other types of simulations can be described in a similar fashion Chapter 11 Priority queues and Heaps 2 Priority Queue Implementation Techniques We will explore three different queue implementation techniques two of which are developed in the worksheets The first is to examine how any variety of ordered bag such as the SortedBag SkipList or AVLtree can be used to implement the priority queue The second approach introduces a new type of binary tree termed the heap The classic heap known simply as the heap provides a very memory efficient representation for a priority queue Our third technique the skew heap uses an interesting variation on the heap technique A note regarding the name heap The term heap is used for two very different concepts in computer science The heap data structure is an abstract data type used to implement priority queues The terms heap heap memory heap allocation and so on are used to describe memory that is allocated directly by the user using the malloc function You should not confuse the two uses of the same term Building a Priority Queue using an Ordered Bag In earlier chapters you have encountered a number of different bag implementation techniques in which the underlying collection was maintained in sequence Examples included the sorted dynamic array the skip list and the AVL tree In each of these containers the smallest element is always the first value While the bag does not support direct access to the first element as does say the queue we can nevertheless obtain access to this value by means of an iterator This makes it very easy to implement a priority queue using an ordered bag as a storage mechanism for the underlying data values as the following addE Simply add the value to the collection using the existing insertion functions first Construct an iterator and return the first value produced by the iterator removeFirst Use the existing remove operation to delete the element returned by first isEmpty Use the existing size operation for the bag and return true if the size is zero We have seen three ordered collections the sorted array the skip list and the AVL tree Based on your knowledge of the algorithmic execution speeds for operations in those data structures fill in the following table with the execution times for the bag heap constructed in a fashion described above I Operation I SortedArray I SkipList I AVLtree I AddnewElement I I Firsto Chapter 11 Priority queues and Heaps 3 removeFirst I A note on Encapsulation There are two choices in developing a new container such as the one described above One choice is to simply add new functions or extend the interface for an existing data structure Sometimes these can make use of functionality already needed for another purpose The balanced binary tree for example already needed the ability to find the leftmost child in a tree in order to implement the remove operation It is easy to use this function to return the first element in the three However this opens the possibility that the container could be used with operations that are not part of the priority queue interface An alternative would have been to create a new data structure and encapsulate the underlying container behind a structure barrier using something like the following struct SortedHeap struct AVLtree data We would then need to write routines to initialize this new structure rather than relying on the existing routines to initialize an AVL tree At the cost of an additional layer of indirection we can then more easily guarantee that the only operations performed will be those defined by the interface There are advantages and disadvantages to both The bottom line is that you as a programmer should be aware of both approaches to a problem and more importantly be aware of the implications of whatever design choice you make Building a Priority Queue using a Heap In a worksheet you will explore two alternative implementation techniques for priority queues that are based around the idea of storing values in a type of representation termed a heap A heap is a binary tree that also maintains the property that the value stored at every node is less than or equal to the values stored at either of its child nodes This is termed the heap order property The classic heap structure known just as the heap adds the additional requirement that the binary tree is complete That is the tree if full except for the bottom row which is filled from left to right The following is an example of such a heap Chapter 11 Priority queues and Heaps 4 V 1 7 399 it D 012345678910 2 3 5 9 10 7 s I12141116 Notice that a heap is partially ordered but not completely In particular the smallest element is always at the root Although we will continue to think of the heap as a tree we will make use of the fact that a complete binary tree can be very efficiently represented as an array To root of the tree will be stored as the first element in the array The children of node i are found at positions 2il and 2i2 the parent at il 2 You should examine the tree above and verify that the transformation given will always lead you to the children of any node To reverse the process to move from a node back to the parent simply subtract 1 and divide by 2 You should also verify that this process works as you would expect We will construct our heap by defining functions that will use an underlying dynamic array as the data container This means that users will first need to create a new dynamic array before they can use our heap functions struct dyArray heap create a new dynamic array dyArrayInit ampheap 10 initialize the array to 10 elements To insert a new value into a heap the value is first added to the end This operation has actually already been written in the function dyArrayAdd Adding an element to the end preserves the complete binary tree property but not the heap ordering To fix the ordering the new value is percolated up into position It is compared to its parent node If smaller the node and the parent are exchanged This continues until the root is reached or the new value finds its correct position Because this process follows a path in a complete binary tree it is Olog n The following illustrates adding the value 4 into a heap then percolating it up until it reaches its final position When the value 4 is compared to the 2 the parent node containing the 2 is smaller and the percolation process halts Chapter 11 Priority queues and Heaps 5 Because the process of percolating up traverses a complete binary tree from leaf to root it is Olog n where n represents the number of nodes in the tree Percolating up takes care of insertion into the heap What about the other operations The smallest value is always found at the root This makes accessing the smallest element easy But what about the removal operation When the root node is removed it leaves a hole Filling this hole with the last element in the heap restores the complete binary tree property but not the heap order property To restore the heap order the new value must percolate down into position To percolate down a node is compared to its children If there are no children the process halts Otherwise the value of the node is compared to the value of the smallest child If the node is larger it is swapped with the smallest child and the process continues with the child Again the process is traversing a path from root to leaf in a complete binary tree It is therefore Olog n In worksheet 33 you will complete the implementation of the priority queue constructed using a heap by providing the functions to percolate values into position but up and down Heap Sort Chapter 11 Priority queues and Heaps 6 When a value is removed from a heap the size of the heap is reduced If the heap is being represented in an array this means that the bottommost element of the array is no longer being used Using the terminology of the dynamic array we examined earlier the size of the collection is smaller but the capacity remains unchanged size ii i3i5i4i8i6i7i9i i ii original heap ii5i4i8i6i7i9i i ii remove front size ii i9i5i4i8i6i7i i i ii movelast siie i4i5i7i8i6i9i i i ii reheap What if we were to store the removed values in the now unused section of the array In fact since the last element in the array is always moved into the hole made by the removal of the root it is a trivial matter to simply swap this value with the root size ii i4i5i7i8i6i9i3i2i1i0i Suppose we repeat this process always swapping the root with the currently last element then reheaping by percolating the new root down into position The result would be a sorting algorithm termed heap sort The following is a snapshot illustrating heap sort in the middle of execution Notice that the smallest elements have been moved to the right The current size of the dynamic array is indicated by the sharp drop in values The Chapter 11 Priority queues and Heaps 7 212mm m m 12 af39hls pm Are axganmdmahzap Nance thank hzapxsnm cam ztelyaxdznd but has a mndzmymwds bung axdzxed Heapsorrmt HJ Ta dztznnmz m dgandqmw execntmn am far this 51mm recs mm mm xeqnues DOB 11 slaps mm m nexecmmns mammm pmduce m mmalhzap mm mm m nfnnhzxexecmmns m xehzap 5 Inng pmcess afmmng Almgethznhz 11me m 5 0n1ag n This matthzs mafmexge sun qmcksan undue 5m EemxyzL 1MP 5m xeqnues m mmm slang Qua Simulate execu an fth Heap mn algaan an m fa awmg Wm 9 3 2 4 5 7 2 5 1 pm mkz m Wm mm a 1m m gmphlcal xepxesemnonn ls pmbablyeagex m umxk wnh than m vecmx farm Than npam ynmave m smallzsl Wm and xeme m 1W Slow Heal xdzxafthz 1m ming children mwm m Duly mdxsdute dzxssmallznhanenhsznsc axgamntmnfmmthz dma 1MP m skzwhzap m2sz m absemnans mm M ldren can alwaysbe exchanged wnh each athzx mm mm mm is mwm 5mm bath mngwa and xemawls mm a 1m snub mplemznmd as spcxdcases afamme gemnhnsk mm m mug m hzapsmtn an cmquot 11 Pmmyquuzsandeaps 2 Inseasym 5 1msz xemnve 5 smhxm smug thmhz sm estuhans mm 212mm 5 Emma ymlm mm m as mmely39he 1m and right child mes Ta buddam 1MP yuncmsxmplymzxge m m Tawewaddmnnas a marge Canada m exxsnng 1W 5 an arguman mu m wnh mm mug mm 5 m secand Marge m m m pmduce m me um m ch59 1MP a 51W mp dues mm um um m bmaxykee ls campxm ung m systematic yswapp Th2 xesulns um Lhm and mhalanced xee cannm xemamsa n snub 51mm Myth mu m m presemzdhne um amamzed mum each apnnanmaskzwhzapxsna vmxs han OOH n m fa awmg alums a mm af qewluz m m an exxshng m Nan2 ham he wnha m xghtpa39hbecamzs am mum 1m pm 1 WWW w a w a m 7 m mug algamhm fax a skew mp can be described as fallnws Nada merge Nude 1m ad right mm 15 mm xemm ngm 39nght 5 null return 1m mm chddwl lt right chddwhlz Nae hemp Mum 1 exge z right we hemp Chapter 11 Pnamyqnulzs AMIleaps 9 ght ught ergehght le le erhp retum ught gt ldeas lek u do they are q apart so that they eauhothave alastrhg rmpaet oh exeeutroh true To measure the relauve performance of the Heap and SkewHeap abstraeuohs an experrrheht was eoholueteolrh whlch h random rhtegers between 0 and 100 were rhserteol obtarhed as follows The result rhdleates that even through the SkewHeap ls performmg th overall Heap Compatleon J ZSOOTtmems Heap Skew mmmmmmro w Short Exercises 1 2 Where ls the smallestvalue fouhdm aheap7 3 Where ls the 2 d smallest element m aheap7 The thud smallest elemeht7 Chapter 11 Phohty queues and Heaps 4 V39 0 gt1 9 gt0 What is the height of a heap that contains 10 elements If you interpret a sorted array as a heap is it guaranteed to have the heap order property Could you implement the tree sort algorithm using a heap Recall that the tree sort algorithm simply copies values from a vector into a container that is the heap the repeatedly removes the smallest element and copies it back to the vector What is the bigoh execution time for this algorithm Suppose you wanted to test the Heap data structure What would be some good boundary value test cases Program a test driver for the Heap data type and execute the operations using the test cases you identi ed in the previous question An operation we have not discussed is the ability to change the value of an item already in the heap Describe an algorithm that could be used for this purpose What is the complexity of your algorithm Analysis Exercises 1 Show that unless other information is maintained nding the maximum value in a heap must be an On operation Hint How many elements in the heap could potentially be the maximum 2 Imagine a heap that contains 2quot values This will naturally represent a complete binary tree Notice that the heap property is retained if the left and right subtrees of any node are exchanged How many different equivalent heaps can be produced using only such swappings 3 Self Study Questions 1 What are the abstract operations that characterize a priority queue 2 Give an example of a priority queue that occurs in a noncomputer science situation 3 Describe how a priority queue is similar to a bag and how it is different Describe how a priority queue is similar to a queue and how it is different 4 Why is a priority queue not a true queue in the sense described in Chapter 7 Chapter 11 Priority queues and Heaps 5 What is discrete event driven simulation How is it related to priority queues 6 What property characterizes the nodes in a heap 7 When a binary tree such as a heap is represented as a dynamic array where are the children of node i What is the index of the parent of node i 8 When a heap is represented in an array why is it important that the tree being represented in complete What happens if this condition is not satis ed 9 Illustrate the process of percolating a value down into position Explain why this operation is Olog n 10 Illustrate the process of percolating a value up into position Explain why this operation is Olog n 11 Place the following values in the order shown into an initially empty heap and show the resulting structure 5 6 4 2 9 7 8 l 3 12 How is a skew heap different from a heap What property of the heap data type does this data structure exploit l3 Perform the same insertions from question 10 into an initially empty skew heap and show the resulting structure Chapter Summary A priority queue is not a true queue at all but is a data structure designed to permit rapid access and removal of the smallest element in a collection One way to build a Key Concepts Ergzlrjty Queue priority queue is to use an ordered collection However Heap order property they can also be constructed us1ng an efficient array H 6 ap son representation and an idea termed the heap A heap 1s a binary tree that supports the heap order property The 0 Skew heap heap order property says that the value stored at every node is smaller than the value stored at either of its child node The classic heap stores elements in a complete binary tree Because the tree is complete it can be represented in an array form without any holes appearing in the collection In addition to providing the basis for implementing a priority queue the heap structure forms the basis of a very efficient sorting algorithm A skew heap is a form of heap that does not have the fixed size characteristic of the vector heap The skew heap data structure is interesting in that it can potentially have a very poor worst case performance However it can be shown that the worst case performance cannot be maintained and following any occurrence the next several Chapter 11 Priority queues and Heaps 12 operations of insertion or removal must be very rapid Thus when measured over several operations the performance of a skew heap is very impressive Programming Exercises N E 4 V39 0 Complete the implementation of the priority queue using a sorted dynamic array as the underlying container This technique allows you to access both the smallest and the largest element with equal ease What is the algorithmic execution time for operations with this representation Consider using a balanced binary tree such as an AVL tree for an implementation technique Recall that as part of the process of removing an element from an AVL tree you needed the ability to find the leftmost child of the right subtree Show how using the ability to identify the leftmost child can be used to find the smallest element in the tree Write priority queue operations based on this observation Complete the implementation of the resturant simulation described in this chapter Initialize your simulation with a number of arrival events selected at random points over the period of an hour Assume that patrons take between five and ten minuets selected randomly between the time they are seated and the time they order Assume that patrons take between 30 to 50 minuits again selected randomly to eat Those patrons who are not able to seat wait on a queue for a table to become available Print out a message every time an event occurs indicating the type of the event and the time for the new events generated by the current event Keep track of the number of patrons serviced in the period of two hours Program an implementation of an airport The airport has two runways Planes arrive and request permission to land and independently planes on the ground request permission to talk off Program a discrete event driven simulation of a hospital emergency room Upon arrival a triage doctor assigns each patient a number based on the severity of his or her harm The room has a fixed number ofbeds As each bed is freed the next most urgent patient is handled Patients take varying amounts of time to handle depending upon their condition Collect statistics on the length of time each patient will have to wait An alternative approach to the skew heap is a leftist heap In a leftist heap the height of the left child is always larger than or equal to the height of the right child As two children in a heap can always be swapped without violating the heaporder property this is an easy condition to impose To construct a leftist heap nodes are modified so as to remember their height We saw how to do this in the AVL tree As with the skew heap all operations on a leftist heap are implemented using the single task of merging two heaps The following steps are used to merge heaps T1 and T2 a If the value in T2 is less than the value in T1 merge in the opposite order Chapter 11 Priority queues and Heaps l3 b The root of T1 is the root of the new heap The right shild is recursively merged with T2 c If the resulting height of the right child is larger than the left child the two children are reversed d The height of the result is set to one lrger than the height of the left child Because the merge is always performed with a right child which is always has a height smaller than the left child the result is produced very quickly Provide an implementation of a heap data structure based on this principle On the Web The wikipedia contains articles explaining the priority queue abstraction as well as the heap data structure and the associated heap sort algorithm The entry for heap contains links to several variations including the skew heap as well as others Wikipedia also contains a good explanation of the concept of Discrete Event Simlation The online Dictionary ofAlgorz39thms and Data Structures contains explanations of heap the heapify algorithm and other topics discussed in this chapter Chapter 11 Priority queues and Heaps l4

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "I made $350 in just two days after posting my first study guide."

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.