Solution

A maximum priority queue stores keyed entries and supports insertion, inspection and removal of an entry with greatest key, and key increases. A max-heap gives the following running times, with the size/capacity cost of the backing array accounted for separately:

maximum: return the root key in $O (1)$ time.
insert: append at the next available leaf, then use sift up until the heap order holds, in $O (lo g n)$ time.
extractMaximum: save the root, replace it by the last entry, reduce the size, and use sift down, in $O (lo g n)$ time.
increaseKey(i,k): reject $k < A [i]$ ; otherwise set the new key and use sift up, in $O (lo g n)$ time.
isEmpty and size: inspect the stored size in $O (1)$ time; construct a queue from $n$ keys by bottom-up heap construction in $Θ (n)$ time.

Empty-queue inspections and removals need an explicit failure result. The index argument to increaseKey must identify the entry's current location: if callers use item handles, update their location records during swaps.

 Ancestors (12)

 View article source

 Discussion (0)

New discussion

There are no discussions about this article yet.

 Articles by others on the same topic (0)

There are currently no matching articles.

  See all articles in the same topic Create my own version

Past exam of the year 1 of the computer science course of the University of Oxford / 2019 / Functional programming, design and analysis of algorithms / 6 / b / Solution

 Ancestors (12)

 Discussion (0)  Subscribe (1)

 Articles by others on the same topic (0)

 Discussion (0)