Heaps Flashcards
A special queue where the key with the highest priority is found at one end
Used to schedule jobs on a computer shared among multiple users
Priority queues
1) the higher the key,
the greater the priority
2) the key indicates
the execution time (lower is faster)
Implementation of priority queues using a linked list
insert – O(1)
delete min – O(n)
Implementation of priority queues using a sorted linked list
insert – O(n)
delete min – O(1)
An array that we can view as a nearly complete binary tree
(Binary) Heap
The tree is full on all levels except possibly
the bottom level (which is filled from left to right)
Each node of the tree is
an element of the array
The number of elements in the heap stored in an attribute
Heap-size
If heap-size = 0,
heap is empty
Given a heap represented by an array 𝐴, the root of the tree is at
𝐴[1]
For any node at index 𝑖,
a. its parent is at
index i / 2
b. its left child is at
index 2𝑖
c. its right child is at
index 2𝑖 + 1
𝐴[𝑝𝑎𝑟𝑒𝑛𝑡(𝑖)] ≥ 𝐴[𝑖]
Max-heap
For every node other than the root, the value of a node is
at most, the value of its parent
The largest value in a max-heap is at
the root
𝐴[𝑝𝑎𝑟𝑒𝑛𝑡(𝑖)] ≤ 𝐴[𝑖]
Min-heap
For every node other than the root, the value of a node is
at least, the value of its parent
The smallest value in a min-heap is at
the root
We insert at the next available location
Heap insertion
Fixup: percolate up aka
Sift-up, float up, *min-heapify
To delete the min/max,
1) swap it with the last key
2) subtract heap-size by 1
3) do a fixup from the root (percolate down)
Converts an array into a min- / max-heap
Starting from index i / 2 down to 1, percolate down
Build min- / max-heap
Using a heap for a priority queue,
insert – O(log n)
delete min/max – O(log n)
build-heap – O(n)
A sorting algorithm that calls build-max-heap, then performs N-1 delete-max operations
Heapsort
