Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

CS21120 Algorithms > Queue and Priority Queue > Flashcards

Queue and Priority Queue Flashcards

1
Q

Array Based Implementation
What is the performance of the enqueue method?

A

Theta 1 (Constant)

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

Array Based Implementation
What is the performance of the dequeue method?

A

Theta 1 (Constant)

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

Array Based Implementation
What is the performance of the peek method?

A

Theta 1 (Constant)

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

Array Based Implementation
What is the performance of the size method?

A

Theta 1 (Constant)

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

Array Based Implementation
What is the performance of the empty method?

A

Theta 1 (Constant)

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

At what end of a list based queue are insertions efficient?

A

The back

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

At what end of a list based queue are removals efficient?

A

The front

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

List Based Implementation
What is the performance of the enqueue method?

A

Theta 1 (Constant)

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

List Based Implementation
What is the performance of the dequeue method?

A

Theta 1 (Const)

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

List Based Implementation
What is the performance of the top method?

A

Theta 1 (Const)

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

List Based Implementation
What is the performance of the size method?

A

Theta 1 (Const)

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

List Based Implementation
What is the performance of the empty method?

A

Theta 1 (Const)

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

Which implementation is more expensive in practice?

A

List based implementation

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

What is the definition of a min heap?

A
  • It is a full binary tree
  • Each child has a value greater than or equal to compared to its parent
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

How do we add an element to a heap?

A
  • Add an element to the next available space in the array
  • Check if the min heap has been violated
  • Climb up to the root, making swaps where needed
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

How do we remove from a heap?

A
  • Swap the minimum and maximum of the heap
  • Remove item at end of array as now can be removed safely
  • Find good candidates to repair heap by following the path of smaller children
  • Climb back up the array, making swaps where needed
17
Q

What are the main methods of a min heap?

A

insert
removeMin

18
Q

What are the worst case runtimes for a min heap’s main methods?

A

insert: theta (log n)
removeMin: theta (log n)

CS21120 Algorithms (5 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions