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/heapsort

We are not interested in the heap as a data structure right now. Let us only focus on the heapsort !


Do now:

Programmer joke:
!false
Explanation:
(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-Heap

MyHeap.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). 


Comments