A Binary Heap is a complete binary tree stored in an array that obeys the heap property:
Because the tree is complete, we can map nodes to indices: for index i, parent p=(i-1)//2, left child 2i+1, right child 2i+2. No pointers required.
O(log n)O(log n)a[i]=new then sift up. (For max-heap, increase-key.) O(log n)O(log n)O(n)| Operation | Time | Space | Notes |
|---|---|---|---|
| insert | O(log n) | O(1) | sift up path length ≤ height |
| extract-min/max | O(log n) | O(1) | sift down |
| decrease/increase-key | O(log n) | O(1) | moves along a root–leaf path |
| delete-index | O(log n) | O(1) | swap-with-last then fix |
| build-heap (Floyd) | O(n) | O(1) | many nodes are near leaves ⇒ cheaper |
| peek | O(1) | — | root at index 0 |
2i+1, 2i+2; parent at (i-1)//2.O(n log n); Floyd’s method is O(n).
class Heap:
def __init__(self): self.a=[] # 0-indexed
def _less(self,i,j): return self.a[i] < self.a[j]
def _swap(self,i,j): self.a[i],self.a[j]=self.a[j],self.a[i]
def _up(self,i):
while i>0:
p=(i-1)//2
if self._less(i,p): self._swap(i,p); i=p
else: break
def _down(self,i):
n=len(self.a)
while True:
l=2*i+1; r=l+1; s=i
if l<n and self._less(l,s): s=l
if r<n and self._less(r,s): s=r
if s==i: break
self._swap(i,s); i=s
def push(self,x):
self.a.append(x); self._up(len(self.a)-1)
def pop(self):
if not self.a: return None
x=self.a[0]; self.a[0]=self.a[-1]; self.a.pop()
if self.a: self._down(0)
return x
def build(self, arr):
self.a=list(arr)
for i in range((len(self.a)//2)-1, -1, -1): self._down(i)
class MaxHeap(Heap):
def _less(self,i,j): return self.a[i] > self.a[j]
import java.util.*;
class MinHeap {
ArrayList<Integer> a = new ArrayList<>();
boolean less(int i,int j){ return a.get(i) < a.get(j); }
void swap(int i,int j){ int t=a.get(i); a.set(i,a.get(j)); a.set(j,t); }
void up(int i){
while(i>0){
int p=(i-1)/2;
if(less(i,p)){ swap(i,p); i=p; } else break;
}
}
void down(int i){
int n=a.size();
while(true){
int l=2*i+1, r=l+1, s=i;
if(l<n && less(l,s)) s=l;
if(r<n && less(r,s)) s=r;
if(s==i) break;
swap(i,s); i=s;
}
}
void push(int x){ a.add(x); up(a.size()-1); }
Integer pop(){
if(a.isEmpty()) return null;
int x=a.get(0);
int last=a.remove(a.size()-1);
if(!a.isEmpty()){ a.set(0,last); down(0); }
return x;
}
void build(List<Integer> arr){
a.clear(); a.addAll(arr);
for(int i=a.size()/2-1;i>=0;--i) down(i);
}
}
#include <vector>
using namespace std;
struct MinHeap{
vector<int> a;
bool less_(int i,int j){ return a[i] < a[j]; }
void swap_(int i,int j){ int t=a[i]; a[i]=a[j]; a[j]=t; }
void up(int i){
while(i>0){ int p=(i-1)/2; if(less_(i,p)){ swap_(i,p); i=p; } else break; }
}
void down(int i){
int n=a.size();
while(true){
int l=2*i+1, r=l+1, s=i;
if(l<n && less_(l,s)) s=l;
if(r<n && less_(r,s)) s=r;
if(s==i) break;
swap_(i,s); i=s;
}
}
void push(int x){ a.push_back(x); up((int)a.size()-1); }
int pop(){
int x=a.front(); a[0]=a.back(); a.pop_back(); if(!a.empty()) down(0); return x;
}
void build(const vector<int>& arr){
a=arr; for(int i=(int)a.size()/2-1;i>=0;--i) down(i);
}
};
heapq (min-heap). For max-heap, push negatives or use a wrapper.PriorityQueue<Integer> (min-heap by default; custom comparator for max-heap).std::priority_queue<T> is max-heap by default; use greater<T> for min-heap.O(log n) swaps.