Binary HeapsReadingsRevisiting FindMinPriority Queue ADTLess flexibility  More speedBetter than a speeding BSTSlide 7Heap order propertyBinary Heap vs Binary Search TreeStructure propertyExamplesArray Implementation of Heaps (Implicit Pointers)FindMin and DeleteMinDeleteMinMaintain the Structure PropertyMaintain the Heap PropertyDeleteMin: Percolate DownPercolate DownDeleteMin: Run Time AnalysisInsertSlide 21Slide 22Insert: Percolate UpInsert: DonePercUpSentinel ValuesBinary Heap AnalysisBuild HeapSlide 29Slide 30Analysis of Build HeapOther Heap OperationsSlide 33Slide 34Slide 35Slide 36PercUp SolutionBinary HeapsCSE 373Data Structures Lecture 1112/26/03 Binary Heaps - Lecture 11 2Readings•Reading ›Sections 6.1-6.412/26/03 Binary Heaps - Lecture 11 3Revisiting FindMin•Application: Find the smallest ( or highest priority) item quickly›Operating system needs to schedule jobs according to priority instead of FIFO›Event simulation (bank customers arriving and departing, ordered according to when the event happened)›Find student with highest grade, employee with highest salary etc.12/26/03 Binary Heaps - Lecture 11 4Priority Queue ADT •Priority Queue can efficiently do:›FindMin (and DeleteMin)›Insert•What if we use…›Lists: If sorted, what is the run time for Insert and FindMin? Unsorted?›Binary Search Trees: What is the run time for Insert and FindMin? ›Hash Tables: What is the run time for Insert and FindMin?12/26/03 Binary Heaps - Lecture 11 5Less flexibility  More speed•Lists›If sorted: FindMin is O(1) but Insert is O(N)›If not sorted: Insert is O(1) but FindMin is O(N)•Balanced Binary Search Trees (BSTs)›Insert is O(log N) and FindMin is O(log N)•Hash Tables›Insert O(1) but no hope for FindMin•BSTs look good but…›BSTs are efficient for all Finds, not just FindMin›We only need FindMin12/26/03 Binary Heaps - Lecture 11 6Better than a speeding BST•We can do better than Balanced Binary Search Trees?›Very limited requirements: Insert, FindMin, DeleteMin. The goals are:›FindMin is O(1)›Insert is O(log N)›DeleteMin is O(log N)12/26/03 Binary Heaps - Lecture 11 7Binary Heaps•A binary heap is a binary tree (NOT a BST) that is:›Complete: the tree is completely filled except possibly the bottom level, which is filled from left to right›Satisfies the heap order property•every node is less than or equal to its children•or every node is greater than or equal to its children•The root node is always the smallest node›or the largest, depending on the heap order12/26/03 Binary Heaps - Lecture 11 8Heap order property•A heap provides limited ordering information•Each path is sorted, but the subtrees are not sorted relative to each other›A binary heap is NOT a binary search tree24675-1010126847These are all valid binary heaps (minimum)12/26/03 Binary Heaps - Lecture 11 9Binary Heap vs Binary Search Tree9410 975 24510 9497 24Binary Heap Binary Search TreeParent is greater than left child, less than right childParent is less than bothleft and right childrenmin valuemin value12/26/03 Binary Heaps - Lecture 11 10Structure property•A binary heap is a complete tree›All nodes are in use except for possibly the right end of the bottom row12/26/03 Binary Heaps - Lecture 11 11Examples264572645not complete624complete tree, heap order is "max"complete tree, heap order is "min"26547complete tree, but minheap order is broken12/26/03 Binary Heaps - Lecture 11 12Array Implementation of Heaps (Implicit Pointers)•Root node = A[1]•Children of A[i] = A[2i], A[2i + 1]•Parent of A[j] = A[j/2]•Keep track of current size N (number of nodes)N = 5valueindex26457- 2 4 6 7 50 1 2 3 4 5 6 71543212/26/03 Binary Heaps - Lecture 11 13FindMin and DeleteMin•FindMin: Easy!›Return root value A[1]›Run time = ?•DeleteMin:›Delete (and return) value at root node2341085714691112/26/03 Binary Heaps - Lecture 11 14DeleteMin3410857146911•Delete (and return) value at root node12/26/03 Binary Heaps - Lecture 11 15Maintain the Structure Property•We now have a “Hole” at the root›Need to fill the hole with another value•When we get done, the tree will have one less node and must still be complete3410857146911341085714691112/26/03 Binary Heaps - Lecture 11 16Maintain the Heap Property•The last value has lost its node› we need to find a new place for it•We can do a simple insertion sort operation to find the correct place for it in the tree341085714691112/26/03 Binary Heaps - Lecture 11 17DeleteMin: Percolate Down• Keep comparing with children A[2i] and A[2i + 1]• Copy smaller child up and go down one level• Done if both children are  item or reached a leaf node• What is the run time?341085714691141085714691138410145769113??12/26/03 Binary Heaps - Lecture 11 18Percolate DownPercDown(i:integer, x: integer): {// N is the number elements, i is the hole, x is the value to insertCase{ 2i > N : A[i] := x; //at bottom// 2i = N : if A[2i] < x then A[i] := A[2i]; A[2i] := x; else A[i] := x; 2i < N : if A[2i] < A[2i+1] then j := 2i; else j := 2i+1; if A[j] < x then A[i] := A[j]; PercDown(j,x); else A[i] := x;}}6 | 10 | 8 | 13 | 14 | 251 2 3 4 5 6no childrenone childat the end2 children12/26/03 Binary Heaps - Lecture 11 19DeleteMin: Run Time Analysis•Run time is O(depth of heap)•A heap is a complete binary tree•Depth of a complete binary tree of N nodes?›depth = log2(N)•Run time of DeleteMin is O(log N)12/26/03 Binary Heaps - Lecture 11 20Insert•Add a value to the tree•Structure and heap order properties must still be correct when we are done8410145769113212/26/03 Binary Heaps - Lecture 11 21Maintain the Structure Property•The only valid place for a new node in a complete tree is at the end of the array•We need to decide on the correct value for the new node, and adjust the heap accordingly8410145769113212/26/03 Binary Heaps - Lecture 11 22Maintain the Heap Property•The new value goes where?•We can do a simple insertion sort operation to find the correct place for it in the tree2841014576911312/26/03 Binary Heaps - Lecture 11 23Insert: Percolate Up28410145769113• Start at last node and keep comparing with parent A[i/2]• If parent larger, copy parent down and go up one level• Done if parent  item or reached top node A[1]• Run time??25841014769113?25810144769113?12/26/03 Binary Heaps - Lecture