Heap / Priority Queue

This is Balanced BT which is Complete BT.
Each element is given a priority. Higher priority element is processed before any lower priority element. Duplicates are allowed. This is suited to be stored in array ie Heap can be implemented using arrays. If you use arrays to implement Heaps then you don’t need to store pointer as done in trees and its space advantage
Complexities Insert: O(logn), Search: O(1), Delete: O(logn)
Process of Heap Creation, Heapify

Max Heap (priority_queue <int>)

Root is always greatest. parent >= child
2nd, 3rd largest element are direct children of root(either left or right).

Min Heap (priority_queue <int, vector <int>, greater <int>>)

Root is always least. Condition: parent <= child.

Code C++ vs Python vs Rust

                       
priority_queue<pair<key, value>> pq
            

let mut max_heap: BinaryHeap<> = 
BinaryHeap::new();                            
                        

let mut max_heap:BinaryHeap <(i32, char)> = 
BinaryHeap::new();
                        

use std::cmp::Reverse;
let mut min_heap: BinaryHeap<Reverse<i32>> = 
BinaryHeap::new();
                        

                       
#Python does not provide built-in heap.
#But it provides heapq module for heap operations on list
import heapq

# Creating a Max Heap
max_heap = []
heapq.heapify(max_heap)  # Convert list into a max heap
            

       
dq.push_back(x)
            

       
max_heap.push(x);
min_heap.push(Reverse(x));
            

       
self.dq.append(x)
            

dq.front()
dq.back()
            

heap.front()
dq.back()
            

self.dq[0]
self.dq[-1]
            

       
dq.pop_front()
dq.pop_back()
            

                   
pub fn pop(&mut self) -> Option <T>
while let Some(top) = max_heap.pop() {
}
if let Some(Reverse(top)) = min_heap.pop(){

}
            

self.dq.pop()
self.dq.popleft()