Heap
Aka: priority queue
A tree structure where all elements meet the heap property (all parent nodes are greater than their children nodes for a max heap)
| Pros | Cons |
|---|---|
| Provides a way to sort data by inserting and removing from a heap | Slower insert/delete times than other structures |
Implementations
Python: heapify
h = [8, 4, 23, 15]
h = heapify(h) # [4, 8, 15, 23]
heappop(h) # [8, 15, 23]
C++: make_heap
std::vector<int> v { 8, 4, 23, 15 }; // [8, 4, 23, 15]
std::make_heap(v.begin(), v.end()); // [4, 8, 15, 23]
std::pop_heap(v.begin(), v.end()); //[8, 15, 23]
Java: Priority Queue
List<Integer> list = Arrays.asList(new String[] {8, 4, 23, 15}); // [8, 4, 23, 15]
PriorityQueue<Integer> pq = new PriorityQueue(list); // [4, 8, 15, 23]
pq.poll(); //[8, 15, 23]
| Operations | Worst | Average |
|---|---|---|
| Delete max | O(log n) | |
| Find max | O(1) | |
| Insert | O(log n) | |
| Update | O(log n) |
