0.0 Insert, FindMax, ExtractMax, IncreaseKey

Question 1

Give the function for the operation:

Insert(x, priority p)

Answer 1

M = M U {x}; x.key = p

Question 2

Give the function for the operation:

element FindMax()

Answer 2

Question 3

Give the function for the operation:

element ExtractMax()

Answer 3

x = FindMax(); M = M{x};
return x

Question 4

Give the function for the operation:

IncreaseKey(x, priority p)

Answer 4

If x.key < p then x.key = p

Question 5

Describe the NaIve implementation of the four operations?

Answer 5

Stored in an array, new elements appended to the end.
Maximum maintained.

Question 6

What are the runtime complexities for the naIve implementation of these four operations?

Answer 6

Insert: O(1)
FindMax: O(1)
ExtractMax: O(n)
IncreaseKey: O(1)

Question 7

Describe the heap implementation of the four operations?

Answer 7

Stored in a heap, new elements appended and sifted down.
Maximum always at root of heap.

Question 8

What are the runtime complexities for the heap implementation of these four operations?

Answer 8

Insert: O(log(n))
FindMax: O(1)
ExtractMax: O(log(n))
IncreaseKey: O(log(n))