Heaps and priority queues

What is the worst-case time for Heapsort to sort an array of n records that each have unique key values?

Θ(nlogn)

Heapsort (as the code is written in this module) is a stable sorting algorithm. Recall that a stable sorting algorithm maintains the relative order of records with equal keys.

false

(Assuming no duplicate key values:) The order of the input records has what impact on the number of comparisons required by Heapsort (as presented in this module)?

There is a constant factor difference

What is the running time of Heapsort when the input is an array where all key values are equal?

Θ(n)

In which cases are the time complexities the same for Heapsort?

Worst and Average

A disadvantage of Heapsort is:

it is not stable (repeated values won’t stay in same order as before)

How much auxilliary space or overhead (beyond the array holding the records) is needed by Heapsort?

Θ(1)

heap is a..? (data structure or abstract data type)

data structure

Priority queue is a..? (data structure or abstract data type)

abstract data type

The tree corresponding to a heap is required to be a complete tree. (true of false)

true

what is max heap?

the value stored at a node is less than or equal to the root (greatest value)

what is a min heap?

the internal value are greater than or equals to the root (smallest value)

height of a complete tree?

h = log n

Peek operation running time for heaps

Θ(1)

worst case running time for insertion and removes for heaps

O(log n)

explain the removal from a min heap

The remove() function will remove the root (smallest number). You replace the root with the last leaf in the tree. Then you percolate the number down if the number is greater than the childrens then you swap with the smallest number until the tree is heapified.

explain the removal from a max heap

the removal() function will remove the root(largest number). You replace the previous root with the last leaf in the tree. if the now root is less than or equal to the children than you swap with the largest number until the tree is heapified.

Build heaps takes? (time complexity) in the worst case.

Θ(n)