Heaps Flashcards

You may prefer our related Brainscape-certified flashcards:
1
Q

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

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

2. Complete binary tree

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

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

  1. Space?
  2. Height?
  3. Insertion?
  4. RemoveMin?
A
  1. O(n)
  2. O(logn)
  3. O(logn)
  4. O(logn)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

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

A
  1. Arraylist-based implementation. The left child is placed at 2i and the right child is placed at 2i+1
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

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

A

O(nlogn)

explanation? Nami angazi

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

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

A
  1. swap the root and the last node
  2. Remove the root at the last node position
  3. Perform downheap
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What is the point of adaptable PQs?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

What does a location-aware entry store?

A
  1. key
  2. position
  3. value
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

In what 2 ways can a APQ be implemented?

A

Arraylist and Heap

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

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

A

analysis table

How well did you know this?
1
Not at all
2
3
4
5
Perfectly