## Priority Queue

- It is an abstract data type such as stack or queue
- But every item has an additional property: a priority value
- Priority Queue is usually implemented with heaps, but it can be implemented with self balancing trees as well
- The highest priority element is retrieved first, no FIFO structure here
- Operation: InsertWithPriority(data, priority), getHighestPriorityElement(), peek()

## Heap

- It is basically a binary tree
- Two main binary heap types: min and max heap
- In a max heap, the keys of parent nodes are always greater than or equal to those of the children, the highest key is in the root node
- It cannot be unbalanced! We insert every new item to the next available place
- Application: Dijkstra algorithm, Prims algorithm

## Heap Sort

- Comparison-based algorithm
- Use heap data structure rather than a linear-time search to find the maximum
- Generally a little bit slower than quick sort, it has the advantage of a more favorable worst-case O(nlogn) runtime
- Does NOT need additional memory
- First we have to construct the heap itself from the numbers we want to sort -> O(n)

Operation | Time Complexity |
---|---|

Find min/max | O(1) |

Remove min/max | O(log(n)) |

Insert | O(log(n)) |

## Implementation

1 | class Heap(object): |

1 | # heap in Python |