Binary Heap Algorithms CS 311 Data Structures and Algorithms Lecture Slides Wednesday November 18 2009 Glenn G Chappell Department of Computer Science University of Alaska Fairbanks CHAPPELLG member ams org 2005 2009 Glenn G Chappell Review Where Are We The Big Problem Our problem for much of the rest of the semester Store a collection of data items all of the same type Operations Access items one item retrieve find all items traverse Add new item insert Eliminate existing item delete All this needs to be efficient in both time and space A solution to this problem is a container Generic containers those in which client code can specify the type of data stored 18 Nov 2009 CS 311 Fall 2009 2 Review Binary Search Trees Efficiency B S T balanced average case Sorted Array B S T worst case Retrieve Logarithmic Logarithmic Linear Insert Logarithmic Linear Linear Delete Logarithmic Linear Linear Binary Search Trees have poor worst case performance But they have very good performance On average If balanced But we do not know an efficient way to make them stay balanced Can we efficiently keep a Binary Search Tree balanced We will look at this question again later 18 Nov 2009 CS 311 Fall 2009 3 Unit Overview Tables Priority Queues Major Topics Introduction to Tables Priority Queues Lots of lousy implementations Binary Heap algorithms Heaps Priority Queues in the C STL 2 3 Trees Other balanced search trees Hash Tables Prefix Trees Tables in various languages 18 Nov 2009 CS 311 Fall 2009 Idea 1 Restricted Table Idea 2 Keep a Tree Balanced Idea 3 Magic Functions 4 Review Introduction to Tables 1 5 Our ultimate value oriented ADT is Table Three primary operations Retrieve by key Insert key data pair Delete by key What do we use a Table for To hold data accessed by key fields For example Customers accessed by phone number Students accessed by student ID number Any other kind of data with an ID code To hold Set data Data in which the only question we ask is whether a key lies in the data set To hold arrays whose indices are not nonnegative integers arr2 hello 3 To hold array like data sets that are sparse arr 6 1 arr 1000000000 2 18 Nov 2009 CS 311 Fall 2009 5 Review Introduction to Tables 2 5 What are possible Table implementations Table A Sequence holding key data pairs Sorted or unsorted Array based or Linked List based Key A Binary Search Tree holding key data pairs Implemented using a pointer based Binary Tree Array Implementations Sorted 2 Ed 4 Bob 9 Ann Linked List Implementations 4 Bob 9 Ann 2 Ed Binary Search Tree Implementation Sorted 2 Ed Unsorted Unsorted 4 Bob 9 Ann 2 Ed 4 Bob 18 Nov 2009 Data 4 Bob 9 Ann 4 Bob 2 Ed 9 Ann CS 311 Fall 2009 9 Ann 2 Ed 6 Review Introduction to Tables 3 5 All of these implementations are lousy All of them that we know how to do have linear time delete Sorted Array Unsorted Array Sorted Linked List Unsorted Linked List Binary Search Tree Balanced Binary Search Tree Retrieve Logarithmic Linear Linear Linear Linear Logarithmic Insert Linear Amortized constant or constant Linear Constant Linear Logarithmic Delete Linear Linear Linear Linear Linear Logarithmic In the table above we allow multiple equivalent keys where it matters Constant time if we have pre allocated enough storage We do not yet know any way to guarantee that the tree will stay balanced unless we can restrict ourselves to read only operations no insert delete 18 Nov 2009 CS 311 Fall 2009 7 Review Introduction to Tables 4 5 In special situations the amortized constant time insertion for an unsorted array and the logarithmic time retrieve for a sorted array can be combined Insert all data into an unsorted array sort the array then use Binary Search to retrieve data This is a good way to handle Table data with separate filling searching phases and few or no deletes Note We will be talking about some complicated Table implementations But sometimes a simple solution is the best 18 Nov 2009 CS 311 Fall 2009 8 Review Introduction to Tables 5 5 Sorted Array Unsorted Array Sorted Linked List Unsorted Linked List Binary Search Tree Balanced how Binary Search Tree Retrieve Logarithmic Linear Linear Linear Linear Logarithmic Insert Linear Constant Linear Constant Linear Logarithmic Delete Linear Linear Linear Linear Linear Logarithmic Idea 1 Restricted Table Perhaps we can do better if we do not implement a Table in its full generality Idea 2 Keep a Tree Balanced Balanced Binary Search Trees look good but how to keep them balanced efficiently Idea 3 Magic Functions Use an unsorted array of key data pairs Allow array items to be marked as empty Have a magic function that tells the index of an item Retrieve insert delete in constant time Actually no but this is still a worthwhile idea We will look at what results from these ideas From idea 1 Priority Queues From idea 2 Balanced search trees 2 3 Trees Red Black Trees B Trees etc From idea 3 Hash Tables 18 Nov 2009 CS 311 Fall 2009 9 Review Priority Queues What a Priority Queue Is A Priority Queue is a restricted access Table Just as a Queue is a restricted Sequence A Priority Queue is not a Queue The key is called the priority We can Retrieve getFront highest priority item Insert any item key data Delete highest priority item 18 Nov 2009 CS 311 Fall 2009 10 Review Priority Queues Applications Implementation A PQ is useful when we have items to process and some are more important than others PQs can be used to do sorting Insert all items then retrieve delete all items The resulting sequence is sorted by priority Note Once again a sorted container gives us a sorting algorithm However as with Insertion Sort instead of using a separate container to sort with we prefer to use an in place version of the algorithm We will call this Heap Sort The most interesting thing about Priority Queues is their usual implementation a Binary Heap 18 Nov 2009 CS 311 Fall 2009 11 Binary Heap Algorithms What is a Binary Heap Definition We define a Binary Heap usually just Heap to be a complete Binary Tree that Is empty Or else 56 The root s key priority is than the key of each of the root s children if any and Each of the root s subtrees is a Binary Heap 50 5 1 25 22 3 10 25 3 11 12 Notes This is a Maxheap If we reverse the order so that the root s key is than the keys of its children we get a Minheap The text presents Heap as an ADT with essentially the same operations as a Priority Queue I am not doing this As we will see a Binary Heap is a good basis for an implementation of