Priority Queues and Heaps
Metodický koncept k efektivní podpoře klíčových odborných kompetencí s využitím cizího jazyka
ATCZ62 - CLIL jako výuková strategie na vysoké škole
C:\Users\21536\AppData\Local\Temp\7zOCBEF4013\interreg_Rakousko_Ceska_Republika_RGB.jpg
https://www.email.cz/download/k/vPwBms0jPnQoTvgo0jFvvGwDhdh9Jlfl9rKdiuyzDRyHOOMId1HvJLvOPRBH2skc4uZ
VKBw/image001.png Fachhochschulen Oberösterreich

C:\Users\21536\AppData\Local\Temp\7zOCBEF4013\interreg_Rakousko_Ceska_Republika_RGB.jpg
https://www.email.cz/download/k/vPwBms0jPnQoTvgo0jFvvGwDhdh9Jlfl9rKdiuyzDRyHOOMId1HvJLvOPRBH2skc4uZ
VKBw/image001.png Fachhochschulen Oberösterreich
Priority Queue – ADT
•A priority queue stores a collection of items
•An item is a pair
(key, element)
•Main methods of the Priority Queue ADT
•insertItem(k, o) - inserts an item with key k and element o
•removeMin() - removes the item with smallest key and returns its element
•Additional methods
•minKey(k, o) minElement() size() isEmpty()
•Applications:
•Standby flyers, Auctions, Stock market

C:\Users\21536\AppData\Local\Temp\7zOCBEF4013\interreg_Rakousko_Ceska_Republika_RGB.jpg
https://www.email.cz/download/k/vPwBms0jPnQoTvgo0jFvvGwDhdh9Jlfl9rKdiuyzDRyHOOMId1HvJLvOPRBH2skc4uZ
VKBw/image001.png Fachhochschulen Oberösterreich
Priority Queue
•Keys in a priority queue can be arbitrary objects on which an order is defined
•Two distinct items in a priority queue can have the same key
•Mathematical concept of total order relation £
•Reflexive property: x £ x
•Antisymmetric property: x £ y Ù y £ x Þ x = y
•Transitive property:  x £ y Ù y £ z Þ x £ z
•Comparator – ADT
•A comparator encapsulates the action of comparing two objects according to a given total order
relation

C:\Users\21536\AppData\Local\Temp\7zOCBEF4013\interreg_Rakousko_Ceska_Republika_RGB.jpg
https://www.email.cz/download/k/vPwBms0jPnQoTvgo0jFvvGwDhdh9Jlfl9rKdiuyzDRyHOOMId1HvJLvOPRBH2skc4uZ
VKBw/image001.png Fachhochschulen Oberösterreich
Heap
•A heap is a binary tree storing keys at its internal nodes and satisfying the following
properties:
•Heap-Order: for every internal node v other than the root,
key(v) ³ key(parent(v))
•Complete Binary Tree: let h be the height of the heap
•for i = 0, … , h - 1, there are 2i nodes of depth i
•at depth h - 1, the internal nodes are to the left of the external nodes
•The last node of a heap is the rightmost internal node of depth h - 1
Last node

C:\Users\21536\AppData\Local\Temp\7zOCBEF4013\interreg_Rakousko_Ceska_Republika_RGB.jpg
https://www.email.cz/download/k/vPwBms0jPnQoTvgo0jFvvGwDhdh9Jlfl9rKdiuyzDRyHOOMId1HvJLvOPRBH2skc4uZ
VKBw/image001.png Fachhochschulen Oberösterreich
Heaps and Priority Queue
•We can use a heap to implement a priority queue
•We store a (key, element) item at each internal node
•We keep track of the position of the last node

C:\Users\21536\AppData\Local\Temp\7zOCBEF4013\interreg_Rakousko_Ceska_Republika_RGB.jpg
https://www.email.cz/download/k/vPwBms0jPnQoTvgo0jFvvGwDhdh9Jlfl9rKdiuyzDRyHOOMId1HvJLvOPRBH2skc4uZ
VKBw/image001.png Fachhochschulen Oberösterreich
Heap – inserting and deleting
•The insertion algorithm consists of three steps
•Find the insertion node z (the new last node)
•Store k at z and expand z into an internal node
•Restore the heap-order property (discussed next)
•The removal algorithm consists of three steps
•Replace the root key with the key of the last node w
•Compress w and its children into a leaf
•Restore the heap-order property (discussed next)
•
Insertion node
w
w

C:\Users\21536\AppData\Local\Temp\7zOCBEF4013\interreg_Rakousko_Ceska_Republika_RGB.jpg
https://www.email.cz/download/k/vPwBms0jPnQoTvgo0jFvvGwDhdh9Jlfl9rKdiuyzDRyHOOMId1HvJLvOPRBH2skc4uZ
VKBw/image001.png Fachhochschulen Oberösterreich
Restoring the heap order
•upheap()
•After the insertion of a new key k, the heap-order property may be violated
•Algorithm upheap restores the heap-order property by swapping k along an upward path from the
insertion node
•Upheap terminates when the key k reaches the root or a node whose parent has a key smaller than or
equal to k
•downheap()
•After replacing the root key with the key k of the last node, the heap-order property may be
violated
•Algorithm downheap restores the heap-order property by swapping key k along a downward path from
the root
•Upheap terminates when key k reaches a leaf or a node whose children have keys greater than or
equal to k
•
•