Module 2: Priority Queues Flashcards Preview

CS 240 MT > Module 2: Priority Queues > Flashcards

Flashcards in Module 2: Priority Queues Deck (16)
Loading flashcards...
1
Q

What is an ADT?

A

It describes storing information and operations on that information

2
Q

What are the operations associated with a stack?

A

Pop and push

Extra operations include size(), isEmpty and top

3
Q

What are the operations associated with a queue

A

enqueue - inserting an item
dequeue - deleting the oldest item

isEmpty, size and front are all extras

4
Q

What is a priority queue?

A

A collection of items/associated operations in which each item has an associated priority

5
Q

What are the operations associated with Priority Queues?

A

Insert - inserts an item associated with a priority

deleteMax - returns and deletes item of highest priority

6
Q

How do you use a priority queue to sort an array

A

Add all items in array to priority queue

Use deleteMax to copy largest items first into the array (starting at index n-1)

7
Q

What is the big-O complexity of priority queue operations if the PQ is implemented using an unsorted array?

A

insert => O(1)

deleteMax => O(n)

8
Q

What is the big-O complexity of priority queue operations if the PQ is implemented using an sorted array?

A

insert => O(n)

deleteMax => O(1)

9
Q

What are the properties of a max-heap?

A

Structural Property - All levels of a heap are completely filled before starting another level and levels are filled from left to right

Heap-Order Property - For any node i, the key of i’s parent is larger than i

10
Q

What is the height of a heap with n nodes?

A

Theta(log(n))

11
Q

How should heaps be stored?

A

As arrays, not as BTs

12
Q

What is the index of a root node of a Heap?

A

A[0]

13
Q

What is the index of a left child in a Heap?

A

A{2i + 1]

14
Q

What is the index of a right child in a Heap?

A

A[2i + 2]

15
Q

What is the parent of node i in a Heap?

A

Floor of (i-1)/2

16
Q

What is the last node in a Heap?

A

A[n - 1]