Courses‎ > ‎APCS - Term 1‎ > ‎Konstantinovich‎ > ‎

### 2019-04-17 Heap Lab

posted Apr 17, 2019, 6:03 AM by Konstantinovich Samuel   [ updated Apr 28, 2019, 1:33 PM ]
 Goal Heapify/heapsortWe are not interested in the heap as a data structure right now. Let us only focus on the heapsort !Do now:Programmer joke:!falseExplanation:(It's funny because it's true)Remember your heap is an array:  (Except with 0 based indexing)How can you heapify this tree: (change it into a valid heap)  Your algorithm should make no assumptions about the values in the tree.Heapify : convert an array into a valid heap(diagrams in class)Heapsort: using any arrya, heapify it, then change it to sorted order.(diagrams in class)Heap Lab:Repo: MKS22X-HeapMyHeap.java   (max heap)//We discussed these 2 methods already:private static void pushDown(int[]data,int size,int index)     - size  is the number of elements in the data array.       - push the element at index i downward into the correct position. This will swap with the larger of the child nodes provided thatchild is larger. This stops when a leaf is reached, or neither child is larger. [ should be O(logn) ]     - precondition: index is between 0 and size-1 inclusive     - precondition: size is between 0 and data.length-1 inclusive.private static void pushUp(int[]data,int index)     - push the element at index i up into the correct position. This will swap it with the parent node until the parent node is larger or the root is reached. [ should be O(logn) ]     - precondition: index is between 0 and data.length-1 inclusive.//We will discuss this today:public static void heapify(int[])    - convert the array into a valid heap. [ should be O(n) ]public static void heapsort(int[])    - sort the array [ should be O(nlogn) ] :     converting it into a heap      removing the largest value n-1 times (remove places at end of the sub-array).