A3 Theory W11 Flashcards
What is a binary heap? [2] State and explain the invariants of a binary heap [4]. What is the primary difference between a min heap and a max heap? [2] Give a drawn example for both [2]
A binary heap is a special type of binary tree, it has at most two child nodes to each parent node and is acyclic.
The main properties of a binary heap are:
- completeness: a binary heap adds elements from left to right to maintain completeness of the heap, this also ensures a binary heap is balanced at all times
- heaps order: a binary heap keeps elements in a particular order depending on wether its a max-heap or min-heap. The root node is either the min or max element of the heap and all elements beneath the root node are either lesser/greater or equal to the parent node.
Min vs max:
- a min-heap has the lowest element as the root node and all elements beneath are either greater than or equal to the root node.
- a max-heap has the highest element as the root node and all elements beneath are either lesser than or equal to the root node.
Example of min-heap:
[10,20,30,40,50,60,70,80]
Example of max-heap:
[80,70,60,50,40,30,20,10]
Given the max heap below, explain the steps of how you will delete the maximum element [10]
To delete the maximum element you will need to follow these steps:
- swap the root node with the last element, in this case you are swapping 44 (root) with 14 (last element)
- remove the max element 44 from the heap and store elsewhere
- you have gotten the max element form the heap but the heap is now not a heap as it’s order is not correct
- first of all, you need to check the indexes of the two children nodes before sinking 14 down
- once checked, you know that 42 is greater than 35 so that will be the new root node
- 14 and 44 are swapped
- repeat this process with 33 and 31
- swap 14 and 33
- now, 14 is almost in the correct position but this time there is only one potential swap as 10 is lesser than 14 but 26 is greater than
- swap 14 and 26 and you have now corrected the heaps ordering after getting the max element
Describe the steps involved in the heapsort algorithm [4] What is the worst-case time complexity of a HeapSort algorithm? [1] Explain your reasoning for the complexity that you chose [3]. How does the complexity of HeapSort compare to the other sorting algorithms we’ve learned in this unit so far (MergeSort and QuickSort) [2]?
Explain the concept of a priority queue. [2]. List and explain its main operations. [2]. Discuss 2 scenarios where a priority queue can be useful [2]. Consider a Priority Queue implemented with a Binary Search tree. State and explain the best and worst-case complexities for its operations. [4]
A priority queue is a queue ADT that has slightly different implementation. It arranges elements based on their priority, an element with high priority is served before an element with low priority. They can be implemented using array lists, linked lists and binary search trees.
Two main operations are:
- add: adds element with a priority
- get_max: gets the max element
Priority queues can be used in:
- airports: airlines use priority queues when seating the passengers
- hospital: hospitals use priority queues while triaging their patients to make sure the patients with highest priority are seen first
Best/worst of complexities:
- add: best and worst is both O(1) as the element is just added to the last cell and length is incremented
- get_max:
- Worst is O(N)Comp , where N is the size of the queue. Need to traverse and compute max element.
- Best is also O(N)Comp, where N is the size of the queue as we need to traverse and compare to find the max
