Priority Queue quiz


What is the expected number of array accesses and compares, respectively, to insert a random key into an ordered array implementation of a priority queue?

logarithmic and logarithmic
logarithmic and linear
linear and logarithmic
linear and linear

Which of the following arrays does not represent a max-oriented binary heap? In other words, which of these arrays is not heap ordered?
J I H G F E D C B A
A A A A A A A A A A
X V U S Q H G J M P
V S N H G F D E I B

Heapsort consists of two steps, heap construction (also called heapification) followed by successive deletions (a.k.a. sortdown or siftdown). How long do these first and second steps take to fully complete?

logarithmic and logarithmic
logarithmic and linear
linear and logarithmic
linear and linear
linearithmic and linear
linear and linearithmic
linearithmic and linearithmic