Binary Heap Data Structure Insights

Cosc 2030 binary Heap.

Binary Heap Binary heap is with the following properties it's a complete tree reminder: all levels are completely filled except for maybe the last one. Either it s a min heap: value of the each node is greater than or equal to the value of its parent with a smallest value at the root max heap: value of each node is less then or equal to the value of its parent with the max value at the root Note, some heaps may require the values inserted to be unique.

Binary Heap (2) The highest or lowest is always at the root, hence the name "heap" This is a sorted structure, but can be only thought as a partially ordered Very useful as a priority queue.

Binary Heap (3) Since this is a complete binary tree, it can be easily represented in an array. We store it by level, with the root in the first position Note some implementations will skip position zero in the array It makes the equations slightly simpler. Why is storing in a array a good thing?

Binary Heap (4) The root is in position zero arr[0] For an ith node, we have the following equations. parent node is located at (i-1)/2 left child is (2*i) +1 right child is (2*i)+2 with i=0 left child is 1, right child is 2 with i=2 left is child is 5, and right is 6. Note, will need to the number of nodes.

Binary Heap (5) A binary heap needs three functions find which is the same as other trees With these two we have to account for min heap or max heap, but the operations. insert delete

insert (with arrays) Insert has two steps 1. add new value to add of the array. 2. "percolation up" We repair the heap property by comparing the added element with it parent and swapping positions as needed. min heap, comparison is parent smaller, swap positions. max heap, comparison is parent larger, swap positions. repeat from new position until the parent comparison is correct or at root level.

Example (max-heap) Start with max-heap Add 7 add to the array at position 5

example (add 7) Check parent of node 5 so (5-1)/2 is position 2 10 is less then 7. no swap needed and done.

Example, add 20 add to the end, array position 6 Check parent of node 6 so (6-1)/2 is position 2 remember, floor/round down. 20 is greater then 10. swap 2 and 6 positions.

Example, add 20 (2) repeat process at new position of 2 Check parent of node 2 so (2-1)/2 is position 0 again, floor/round down. 20 is greater then 17. swap 17 and 20 positions.

Example, add 20 (3) repeat process at new position of 0 position zero is the root done, max-heap property has been restored.

Code for "percolation up"/heapify void maxHeap::heapify(int pos) { if (pos ==0) return; //top, we are done int par = parent(pos); //find the parent position if (par < 0) return; //don't go outside the array bounds. if (heap[pos] > heap[par]) {//child is bigger then parent, so swap swap(pos, par); heapify(par); //call heapify again with new position. } }

delete/remove 1. Delete always removes head value. If the tree is not empty, find a replacement. 2. Replacement is the last position "percolation down" We repair the heap property by comparing the element with both children and swapping positions as needed. if position has no children, stop. min heap, comparison is (smallest of) child smaller, swap positions. max heap, comparison is (largest of) child larger, swap positions. repeat from new position until it's the leaf node or heap property has been repaired.

Example deleteMax Starting with our current tree So remove 20 and use the heap size to find the last position, which is 6. since it's not empty, move value at position 6 to position 0 and check is the heap property needs repaired.

Example deleteMax (2) position 0 has less then a (both) child, so max heap property needs repaired. left child is (2*i) +1 is 1 right child is (2*i)+2 is 2 right child 2, has is larger, so swap position 2 and 0

Example deleteMax (3) position 2 has one child left child is (2*i) +1 is 5 child 5 is less then it's parent, position 2. max heap property has been repaired, so stop.

Example deleteMax again Starting with our current tree So remove 17 and use the heap size to find the last position, which is 5. since it's not empty, move value at position 5 to position 0 and check is the heap property needs repaired.

Example deleteMax again (2) position 0 has less then a (both) child, so max heap property needs repaired. left child is (2*i) +1 is 1 right child is (2*i)+2 is 2 left child 1, has is larger, so swap position 1 and 0

Example deleteMax again (2) position 1 has less then the right child, so max heap property needs repaired. left child is (2*i) +1 is 3 right child is (2*i)+2 is 4 right child 4, has is larger, so swap position 4 and 1

Example deleteMax again (3) position 4 has no children left child is (2*i) +1 is greater then size right child is (2*i)+2 is greater then size max heap property has been repaired.

code for "percolation down" void maxHeap::maxHeapify(int par) { int l = leftc(par); //find left child int r = rightc(par); //find right child int larger = par; //check the left child first if (l <size && heap[l] > heap[larger]) larger = l; //left is larger then parent if (r <size && heap[r] > heap[larger]) larger = r; //right child is larger then left and/or parent. if (larger != par) { //if not parent swap(par, larger); maxHeapify(larger); // move it down. } }

Priority queue Most priority queues are implemented a binary heap reminder binary heap insert and delete are about log2n using a standard list for a priority queue reminder insert or search/delete is linear in timing. Why choose a binary heap over a list/queue?

Priority queue note If the items in the priority queue are unchangeable, then this works great. If the items can be changed then the changed we need run heap repair on the new node to repair the heap. Say we enter 'a' with a priority of 2 and then change the priority of 'a' to 4.

is a binary tree a heap? properties of a heap 1. must be complete. 2. min/max heap property. min heap: value of the each node is greater than or equal to the value of its parent with a smallest value at the root max heap: value of each node is less then or equal to the value of its parent with the max value at the root We can check With a binary tree, starting a root If has children and is heap property satisfied? (example max: is greater then both children) If yes, recursively go down both child. if no, return "false" if no children, return true. This needs be an extra check is this leaf is lower then the left most leaf for complete.

example max heap a b

is a binary tree a heap? (2) If the tree is an array then is a heap? The complete check has likely already been done, unless you can leave blanks in the array. We can loop using this for (i=0; i<=(n-2)/2) ;i++) use i to position and check left/right children return false if property fails return true if we finish the loop. If the tree is not stored in an array, much harder Find out if it is a complete (or nearly complete tree) Then check the max/min property.

is a binary tree a heap? (3) recursive function using an array (array bounds check is missing and should be used). bool isHeap(int arr[], int i, int n) { If a leaf node if (i > (n - 2)/2) return true; If an internal node and is greater than its children, and same is recursively true for the children if (arr[i] >= arr[left(i)] && arr[i] >= arr[right(i)] && isHeap(arr, left(i), n) && isHeap(arr,right(i), n)) return true; return false; }

Last note There is a sort, called heap sort based on a binary heap. we will come back to the heap sort and look at how it works.

QA &