3.1 Heap Sort Flashcards
What is a data structure?
Concept to store and arrange data, so that they (data) can be found and changed efficiently
What is an abstract data type
The ‘interface’ i.e. what operations are supported
What is meant by the implementation of a data structure?
How the features are realised i.e. How is the data stored? What algorithms implement operations?
What is a well packed tree
A binary tree where it is completely filled except maybe the last level which is filled from left to right
What is the array that would store this well pack tree. also write the indexes below the array for each element
Array = [16,14,10,8,7,3,9,2,1,4]
Index = [1,2,3,4,5,6,7,8,9,10]
Indexes start from 1 for arrays
How do you calculate the children of an element?
Multiply its index by 2 to get the first child and multiply by 2 and add 1 to get the second child
How do you calculate the parent of an element?
Divide index by 2 (may have to round down if it is a decimal)
What is a heap?
A heap is an array corresponding to a binary tree, for which all levels are full (except maybe the last one which is filled left to right)
What does it mean if a heap has the ‘max-heap’ property?
If every node’s (except the root) parent is greater than equal to it. This is called a max-heap
What is a min-heap
Every node’s parent is smaller than or equal to it (except the root which doesn’t have a parent)
How can you achieve a max heap with a time complexity of n(logn)
Merge sort
What is a more efficient way of achieving a max-heap?
Work bottom-up and if the node’s parent is less than the node, swap them. You may have to switch another node below that if the original swap breaks a sub-tree lower down
How do you go about fixing a broken sub-tree as a result of a bottom up swap
A recursive subroutine (called MaxHeapify) is called. This routine works top-down. This subroutine checks to see if that tree is correct, if not it swaps the two nodes and then calls itself on the index of the node that was just swapped.
This function starts at the original node that was swapped and makes it’s way down the tree from there making sure none of the subtrees below have been broken.
What is the runtime complexity of the top-down MaxHeapify function and explain why?
The furthest it can move (most it can be called) is the height of the tree which is log(n)
Write the pseudo-code to turn a well packed tree into a max heap. And explain it. The BuildMaxHeap function.
BuildMaxHeap(int A[])
for i = (A.length/2) downto 1
MaxHeapify(A,i)
The first parent to check will be A.length / 2 as you divide index by 2 to find parent and A.lenght will be the last node in the tree (furthest right on the lowest level)
ROUGHLY What is the runtime complexity for the BuildMaxHeap function? Explain why
Loops through the entire tree (n complexity). MaxHeapify (log(n) complexity is in the loop therefore time complexity is n * log(n)
PRECISELY what is the runtime for BuildMaxHeap
Theta(n)
How do you FindMax() of a maxHeap?
Return the root node
How do you ExtractMax() of a max heap?
Copy the root node. Insert the last node on the bottom level as the root node. Remove the last node from the bottom level. Reduce the size of the heap. MaxHeapify() from the root node.
What is the runtime complexity of ExtractMax()
O(log(n)) because of MaxHeapify() function
How do you IncreaseKey() of a max heap?
One of the bottom nodes is increased. Use a while loop to keep swapping it up the tree until it is less than the parent node.
What is runtime complexity of IncreaseKey()
log(n) as the max swaps is the height of the tree. No MaxHeapify() is needed.
How do you Insert() in to a max heap?
Add -inf to the bottom level. Call IncreaseKey() on that element. Runtime complexity is log(n) due to IncreaseKey().
How to completely sort an array using a heap?
Call BuildMaxHeap() function to make sure you have a max heap. Loop through the array calling ExtractMax() and moving it to the end of the array. End up with a fully sorted ascending array.
