13 Priority Queues Sorting

Question 1

Priority Queue

Answer 1

A data structure for maintaing a set of elements, each with an associated value called a key.

Question 2

A max-priority queue supports the following operations:

Answer 2

INSERT - Inserts a new element into the set.

EXTRACT-MAX - removes and returns the element with the largest key.

INCREASE-KEY - increases the value of element key to the new value which is assummed to be at least as largest as currency key value.

Question 3

Priority Queues Operations Running times:

Answer 3

O(log n)

Question 4

MAX-HEAPIFY Running Time

Answer 4

O(log n)

Question 5

BUILD MAX-HEAP Running Time

Answer 5

O(n)

Question 6

HEAP-SORT

Answer 6

O(n log n)

Question 7

Insertion Sort

Answer 7

A variation of priority queue sorting where the priority queue is implemented with a sorted array.

O(n^2)

Question 8

Selection Sort

Answer 8

A variation of priority queue sorting where the priority queue is implemented with a unsorted array.

O(n^2)

Question 9

Heapsort

Answer 9

A variation of priority queue sorting where the priority queue is implemented with a binary heap.

n insertions takes O(n) time
n removals take O(n log n) time