Priority Queue

Question 1

Priority Queue Implemented using ?

Answer 1

-Heaps

-It is often useful to assign a priority to different data items, so that urgent items can be processed first
Ex: ◦ Time in a to do list

Question 2

Priority Queue

Answer 2

§ A priority queue is a data structure for maintaining a set of elements where:

◦ Each element is associated with a value (or priority) called key
◦ The key with the highest (or lowest) priority is extracted first

Question 3

Operations on Max Priority Queues

Answer 3

§Max-priority queues support the following operations:
◦ INSERT(S, x)
——Inserts the element x into the set S

◦ EXTRACT-MAX(S)
——Removes and returns the element of S with the largest key

◦ MAXIMUM(S)
——Returns the element of S with the largest key

◦ INCREASE-KEY(S, x, k)
——Increases the value of element x’s key to the new value k, which is assumed to be at least as large as x’s current key value

Question 4

Operations on Min Priority Queues

Answer 4

◦ INSERT(S, x)
◦ EXTRACT-MIN(S)
◦ MINIMUM(S)
◦ DECREASE-KEY(S, x, k)

Question 5

Delete Maximum (Heap Extract Max) O(logn)

Answer 5

HEAP-EXTRACT-MAX(A)

if heap-size(A) < 1 then
error “heap underflow” max ← A[1]
A[1] ← A[heap-size(A)]
heap-size(A) ← heap-size(A) – 1
HEAPIFY-DOWN(A, 1) {we swapped it with a smaller value than the previous maximum to we need to heaping this root down to maintain the heap property}
return max

Question 6

Heap Increase Key O(logn)

Answer 6

§Goal: Increases the key of an element i in the heap

§ Idea:
◦ Increment the key of A[i] to its new value
◦ If the max-heap property does not hold anymore, heapify-up

HEAP-INCREASE-KEY(A, i ,key)
  if key < A[i] then
         error “new key is smaller   than current key”
  A[i] ← key
  Heapify-up(A, i)

Question 7

Inserting an element (Max-Heap-Insert) O(logn)

Answer 7

§Goal: Inserts a new element into a max-heap

§Idea:
o Expand the max-heap with a new element whose key is -∞
o Calls HEAP-INCREASE-KEY to set the key of the new node to its correct value and maintain the max-heap property

MAX-HEAP-INSERT(A, key)
heap-size(A) ← heap-size(A) + 1
A[heap-size(A)] ← -∞
HEAP-INCREASE-KEY(A, heap-size(A), key)

Question 8

Operations on Heaps

IMPORTANT!!!

Answer 8

◦ MAX-HEAPIFY - O(logn)
◦ BUILD-MAX-HEAP -  O(n) 
◦ HEAP-SORT - O(nlogn)
◦ MAX-HEAP-INSERT- O(logn)
◦ HEAP-EXTRACT-MAX - O(logn)
◦ HEAP-INCREASE-KEY - O(logn)
◦ HEAP-MAXIMUM- O(1)