Heaps

Question 1

What are the properties of a heap ADT? (2)

Answer 1

1. key(v) <= key(parent(v))

2. Complete binary tree

Question 2

What is the big Oh for a heap for the following:

1. Space?
2. Height?
3. Insertion?
4. RemoveMin?

Answer 2

1. O(n)
2. O(logn)
3. O(logn)
4. O(logn)

Question 3

What different ways are there to implement a heap? Give a brief description of operations for each.

Answer 3

1. Arraylist-based implementation. The left child is placed at 2i and the right child is placed at 2i+1

Question 4

What is heap-sort? Give its runtime complexity and an explanation of why it is that value?

Answer 4

O(nlogn)

explanation? Nami angazi

Question 5

What are the 3 steps of removing a node in a heap?

Answer 5

1. swap the root and the last node
2. Remove the root at the last node position
3. Perform downheap

Question 6

Bottom-up heap construction run-time algorithm? Why is it better than just inserting it into a heap?

Answer 6

Runtime algo is O(n), yet the inserting n times into a heap would yield O(nlogn). So BU construction is faster

Question 7

What is the point of adaptable PQs?

Answer 7

When we have a priority queue but we want to make edits to the keys or values of the entries. APQ are an extension of PQs

Question 8

State and explain the methods that are found in a APQ but not a PQ

Answer 8

remove(k) : Will remove an entry with the key k and return the value
replaceKey(e,k)
replaceValue(e,v)

Question 9

What is the point of location-aware entries in an APQ?

Answer 9

So that traversals/searching are not necessary since the position will make future updated easier

Question 10

What does a location-aware entry store?

Answer 10

1. key
2. position
3. value

Question 11

In what 2 ways can a APQ be implemented?

Answer 11

Arraylist and Heap

Question 12

State the difference between the runtimes of arraylist vs heap APQ implementation

Answer 12

analysis table