Waste less time on Facebook — follow Brilliant.
×

Abstract Data Types

ADTs classify data structures based on usage and behavior, providing an understanding of the interface and responses.

Heap/Priority Queue

     

A complete binary min-heap is made by including each integer \([1, 511]\) exactly once. The depth of a node in the heap is the length of the path from the root of the heap to that node. What is the maximum depth at which the number \(11\) can appear?

Details and Assumptions

-The root is at depth \(0\)

Consider the two following implementations of the heap abstract data structure

1. Array Based: An array is maintained in which the element with the highest priority is kept at a certain location.

2. Heap Based: A complete binary heap is implemented and the element with the highest priority is kept at the root of the heap.

Suppose we define a method insert(value) that inserts the new element with the highest priority into the queue.

If \(T_1(n) = O(f(n))\) and \(T_2(n) = O(g(n))\) describe the run times of the insert(value) method for implementation \(1\) and \(2\) respectively, what is the value of \(f(1000) + g(2) \)?

Consider the following tree representation of a heap. It is graphical representation of an array based max-heap and the numbers represent indices of the array, while the alphabets are the actual keys of the heap.

image

image

Suppose we want to insert the letter 'H' into this heap. Which of the following indices could it possibly have without violating the heap condition.

×

Problem Loading...

Note Loading...

Set Loading...