What is stored in Priority Queue

It stores a set of objects (pointers), which point to nodes with a field key.

На чём её можно построить:

• На обычном массиве;

• На min/max-куче (т.е. двоичной куче)

• На d-ичной куче (d-ary heap)

• На Фиббоначиевой куче

  

  Algorithms - Dasgupta, C. H. Papadimitriou, and U. V. Vazirani (2006)

Operations

Max Priority Queue is built on the Max Heap. It supports these operations:

• insert(x, key) - insert element x with key (i.e. priority) key
• max() - pick the maximum element from a priority queue
• extractMax() - pick and pop the maximum element from a priority queue
• increaseKey(x, newKey) - increases the value of element x’s key to the new value newKey, which is assumed to be at least as large as x’s current key value.

As for the Min Priority Queue, it supports insert, min, extractMin and decreaseKey operations.

Реализация на двоичной куче (min/max-heap)

Operations realization

insert(x, key), max() and extractMax() are the same as in max-heap.

increaseKey

void increaseKey(index, newKey) {
	if (arr[index]->key > newKey) {
		return; 
	}
	
	arr[index]->key = newKey; 
	siftUp(index); 
}

Complexity increaseKey — $O(\log{n})$