Waste less time on Facebook — follow Brilliant.
×
Back to all chapters

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, 2000]\) 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 a complete binary heap where 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.

What is the run time for insert(8)?

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.

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

×

Problem Loading...

Note Loading...

Set Loading...