Question 1Consider a minheap that is presented as a tree below:Select all the correct facts from the list below.5 pointsThe minheap property is that each element is smaller than its left child and larger than its right child. This property is not satisfied by the example above.The second smallest element of a minheap is always the second element in the arrayThe minheap property is that each element is smaller than or equal to its children (if they exist). The example above satisfies the minheap property.If an element 2 is inserted into the heap at the end of the array, as the left child of the element 6, the min heap property will continue to be true.The heap when written as an array will be [-5, 8, 4, 12, 10, 6, 19, 13, 17, 11, 12]The second smallest element of a minheap is always the smaller of the two children of the root node.

What are the necessary condition for a Tree to be a heap?a.The tree must be completeb.Every node must follow left or right valuesc.The tree must be compete and root node value is greater or smaller than the children’s valued.Every root node value is greater or smaller than the children’s value

Operations of Heap Data Structure:

Which of the following is the valid min heap?

Cheat SheetThis is a compilation of worst-case complexities for various data-structures and algorithms.Data-StructuresData Structure Worst Case Complexity NotesArray Insert O(1)Retrieve O(1)Linked List Insert at Tail O(n)Insert at Head O(1)Retrieve O(n)Note that if new elements are added at the head of the linkedlist then insert becomes a O(1) operation.Binary Tree Insert O(n)Retrieve O(n)In worst case, the binary tree becomes a linked-list.Dynamic Array Insert O(1)Retrieve O(1)Note by retrieving it is implied we are retrieving from a specific index of the array.Stack Push O(1)Pop O(1)There are no complexity trick questions asked for stacks or queues. We only mention them here for completeness. The two data-structures are more important from a last-in last-out (stack) and first in first out (queue) perspective.Queue Enqueue O(1)Dequeue O(1)Priority Queue (binary heap) Insert O(lgn)Delete O(lgn)Get Max/Min O(1)Hashtable Insert O(n)Retrieve O(n)Be mindful that a hashtable's average case for insertion and retrieval is O(1)B-Trees Insert O(logn)Retrieve O(logn)Red-Black Trees Insert O(logn)Retrieve O(logn)AlgorithmsCategory Worst Case Complexity NotesSorting Bubble Sort O(n2)Insertion Sort O(n2)Selection Sort O(n2)Quick Sort O(n2)Merge Sort O(nlgn)Note, even though worst case quicksort performance is O(n2) but in practice quicksort is often used for sorting since its average case is O(nlgn).Trees Depth First Search O(n)Breadth First Search O(n)Pre-order, In-order, Post-order Traversals O(n)n is the total number of nodes in the tree. Most tree-traversal algorithms will end up seeing every node in the tree and their complexity in the worst case is thus O(n).

Which element is moved during the insertion of a new element into a Max Heap?