// A binary heap is stored in a flat slice. For the node at index i:
// left child = 2i+1, right child = 2i+2, parent = (i-1)/2.
// The heap invariant: every parent is <= its children, so the min is at index 0.
type MinHeap struct {
data []int
}// A binary heap is stored in a flat slice. For the node at index i:
// left child = 2i+1, right child = 2i+2, parent = (i-1)/2.
// The heap invariant: every parent is <= its children, so the min is at index 0.
type MinHeap struct {
data []int
}
// Append at the end — that keeps the tree "complete", but may break the
// invariant, since the new leaf could be smaller than its parent.// A binary heap is stored in a flat slice. For the node at index i:
// left child = 2i+1, right child = 2i+2, parent = (i-1)/2.
// The heap invariant: every parent is <= its children, so the min is at index 0.
type MinHeap struct {
data []int
}
func (h *MinHeap) Push(x int) {
// Append at the end — that keeps the tree "complete", but may break the
// invariant, since the new leaf could be smaller than its parent.
h.data = append(h.data, x)
}// A binary heap is stored in a flat slice. For the node at index i:
// left child = 2i+1, right child = 2i+2, parent = (i-1)/2.
// The heap invariant: every parent is <= its children, so the min is at index 0.
type MinHeap struct {
data []int
}
func (h *MinHeap) Push(x int) {
// Append at the end — that keeps the tree "complete", but may break the
// invariant, since the new leaf could be smaller than its parent.
h.data = append(h.data, x)
// Bubble the newcomer up until it's >= its parent again.
}// A binary heap is stored in a flat slice. For the node at index i:
// left child = 2i+1, right child = 2i+2, parent = (i-1)/2.
// The heap invariant: every parent is <= its children, so the min is at index 0.
type MinHeap struct {
data []int
}
func (h *MinHeap) Push(x int) {
// Append at the end — that keeps the tree "complete", but may break the
// invariant, since the new leaf could be smaller than its parent.
h.data = append(h.data, x)
// Bubble the newcomer up until it's >= its parent again.
h.up(len(h.data) - 1)
}// A binary heap is stored in a flat slice. For the node at index i:
// left child = 2i+1, right child = 2i+2, parent = (i-1)/2.
// The heap invariant: every parent is <= its children, so the min is at index 0.
type MinHeap struct {
data []int
}
func (h *MinHeap) Push(x int) {
// Append at the end — that keeps the tree "complete", but may break the
// invariant, since the new leaf could be smaller than its parent.
h.data = append(h.data, x)
// Bubble the newcomer up until it's >= its parent again.
h.up(len(h.data) - 1)
}
// The min lives at the root. Swap it with the last leaf so we can remove it
// from the end cheaply.// A binary heap is stored in a flat slice. For the node at index i:
// left child = 2i+1, right child = 2i+2, parent = (i-1)/2.
// The heap invariant: every parent is <= its children, so the min is at index 0.
type MinHeap struct {
data []int
}
func (h *MinHeap) Push(x int) {
// Append at the end — that keeps the tree "complete", but may break the
// invariant, since the new leaf could be smaller than its parent.
h.data = append(h.data, x)
// Bubble the newcomer up until it's >= its parent again.
h.up(len(h.data) - 1)
}
func (h *MinHeap) Pop() int {
// The min lives at the root. Swap it with the last leaf so we can remove it
// from the end cheaply.
n := len(h.data) - 1
h.data[0], h.data[n] = h.data[n], h.data[0]
min := h.data[n]
}// A binary heap is stored in a flat slice. For the node at index i:
// left child = 2i+1, right child = 2i+2, parent = (i-1)/2.
// The heap invariant: every parent is <= its children, so the min is at index 0.
type MinHeap struct {
data []int
}
func (h *MinHeap) Push(x int) {
// Append at the end — that keeps the tree "complete", but may break the
// invariant, since the new leaf could be smaller than its parent.
h.data = append(h.data, x)
// Bubble the newcomer up until it's >= its parent again.
h.up(len(h.data) - 1)
}
func (h *MinHeap) Pop() int {
// The min lives at the root. Swap it with the last leaf so we can remove it
// from the end cheaply.
n := len(h.data) - 1
h.data[0], h.data[n] = h.data[n], h.data[0]
min := h.data[n]
// Drop the old min, then sift the leaf that's now at the root back down.
}// A binary heap is stored in a flat slice. For the node at index i:
// left child = 2i+1, right child = 2i+2, parent = (i-1)/2.
// The heap invariant: every parent is <= its children, so the min is at index 0.
type MinHeap struct {
data []int
}
func (h *MinHeap) Push(x int) {
// Append at the end — that keeps the tree "complete", but may break the
// invariant, since the new leaf could be smaller than its parent.
h.data = append(h.data, x)
// Bubble the newcomer up until it's >= its parent again.
h.up(len(h.data) - 1)
}
func (h *MinHeap) Pop() int {
// The min lives at the root. Swap it with the last leaf so we can remove it
// from the end cheaply.
n := len(h.data) - 1
h.data[0], h.data[n] = h.data[n], h.data[0]
min := h.data[n]
// Drop the old min, then sift the leaf that's now at the root back down.
h.data = h.data[:n]
h.down(0)
return min
}// A binary heap is stored in a flat slice. For the node at index i:
// left child = 2i+1, right child = 2i+2, parent = (i-1)/2.
// The heap invariant: every parent is <= its children, so the min is at index 0.
type MinHeap struct {
data []int
}
func (h *MinHeap) Push(x int) {
// Append at the end — that keeps the tree "complete", but may break the
// invariant, since the new leaf could be smaller than its parent.
h.data = append(h.data, x)
// Bubble the newcomer up until it's >= its parent again.
h.up(len(h.data) - 1)
}
func (h *MinHeap) Pop() int {
// The min lives at the root. Swap it with the last leaf so we can remove it
// from the end cheaply.
n := len(h.data) - 1
h.data[0], h.data[n] = h.data[n], h.data[0]
min := h.data[n]
// Drop the old min, then sift the leaf that's now at the root back down.
h.data = h.data[:n]
h.down(0)
return min
}
// up: while a node is smaller than its parent, swap them and follow it upward.// A binary heap is stored in a flat slice. For the node at index i:
// left child = 2i+1, right child = 2i+2, parent = (i-1)/2.
// The heap invariant: every parent is <= its children, so the min is at index 0.
type MinHeap struct {
data []int
}
func (h *MinHeap) Push(x int) {
// Append at the end — that keeps the tree "complete", but may break the
// invariant, since the new leaf could be smaller than its parent.
h.data = append(h.data, x)
// Bubble the newcomer up until it's >= its parent again.
h.up(len(h.data) - 1)
}
func (h *MinHeap) Pop() int {
// The min lives at the root. Swap it with the last leaf so we can remove it
// from the end cheaply.
n := len(h.data) - 1
h.data[0], h.data[n] = h.data[n], h.data[0]
min := h.data[n]
// Drop the old min, then sift the leaf that's now at the root back down.
h.data = h.data[:n]
h.down(0)
return min
}
// up: while a node is smaller than its parent, swap them and follow it upward.
func (h *MinHeap) up(i int) {
for i > 0 {
parent := (i - 1) / 2
if h.data[parent] <= h.data[i] {
break // parent already <= node: invariant restored
}
h.data[parent], h.data[i] = h.data[i], h.data[parent]
i = parent
}
}// A binary heap is stored in a flat slice. For the node at index i:
// left child = 2i+1, right child = 2i+2, parent = (i-1)/2.
// The heap invariant: every parent is <= its children, so the min is at index 0.
type MinHeap struct {
data []int
}
func (h *MinHeap) Push(x int) {
// Append at the end — that keeps the tree "complete", but may break the
// invariant, since the new leaf could be smaller than its parent.
h.data = append(h.data, x)
// Bubble the newcomer up until it's >= its parent again.
h.up(len(h.data) - 1)
}
func (h *MinHeap) Pop() int {
// The min lives at the root. Swap it with the last leaf so we can remove it
// from the end cheaply.
n := len(h.data) - 1
h.data[0], h.data[n] = h.data[n], h.data[0]
min := h.data[n]
// Drop the old min, then sift the leaf that's now at the root back down.
h.data = h.data[:n]
h.down(0)
return min
}
// up: while a node is smaller than its parent, swap them and follow it upward.
func (h *MinHeap) up(i int) {
for i > 0 {
parent := (i - 1) / 2
if h.data[parent] <= h.data[i] {
break // parent already <= node: invariant restored
}
h.data[parent], h.data[i] = h.data[i], h.data[parent]
i = parent
}
}
// down: repeatedly swap a node with its SMALLEST child until it sits above both.
// Assume i is smallest, then check its two children.// A binary heap is stored in a flat slice. For the node at index i:
// left child = 2i+1, right child = 2i+2, parent = (i-1)/2.
// The heap invariant: every parent is <= its children, so the min is at index 0.
type MinHeap struct {
data []int
}
func (h *MinHeap) Push(x int) {
// Append at the end — that keeps the tree "complete", but may break the
// invariant, since the new leaf could be smaller than its parent.
h.data = append(h.data, x)
// Bubble the newcomer up until it's >= its parent again.
h.up(len(h.data) - 1)
}
func (h *MinHeap) Pop() int {
// The min lives at the root. Swap it with the last leaf so we can remove it
// from the end cheaply.
n := len(h.data) - 1
h.data[0], h.data[n] = h.data[n], h.data[0]
min := h.data[n]
// Drop the old min, then sift the leaf that's now at the root back down.
h.data = h.data[:n]
h.down(0)
return min
}
// up: while a node is smaller than its parent, swap them and follow it upward.
func (h *MinHeap) up(i int) {
for i > 0 {
parent := (i - 1) / 2
if h.data[parent] <= h.data[i] {
break // parent already <= node: invariant restored
}
h.data[parent], h.data[i] = h.data[i], h.data[parent]
i = parent
}
}
// down: repeatedly swap a node with its SMALLEST child until it sits above both.
func (h *MinHeap) down(i int) {
n := len(h.data)
for {
// Assume i is smallest, then check its two children.
smallest, l, r := i, 2*i+1, 2*i+2
if l < n && h.data[l] < h.data[smallest] {
smallest = l
}
if r < n && h.data[r] < h.data[smallest] {
smallest = r
}
if smallest == i {
break // node is already <= both children
}
h.data[i], h.data[smallest] = h.data[smallest], h.data[i]
i = smallest
}
}# A binary heap is stored in a flat list. For the node at index i:
# left child = 2i+1, right child = 2i+2, parent = (i-1)//2.
# The heap invariant: every parent is <= its children, so the min is at index 0.
class MinHeap:
def __init__(self):
self.data = []# A binary heap is stored in a flat list. For the node at index i:
# left child = 2i+1, right child = 2i+2, parent = (i-1)//2.
# The heap invariant: every parent is <= its children, so the min is at index 0.
class MinHeap:
def __init__(self):
self.data = []
# Append at the end — that keeps the tree "complete", but may break the
# invariant, since the new leaf could be smaller than its parent.# A binary heap is stored in a flat list. For the node at index i:
# left child = 2i+1, right child = 2i+2, parent = (i-1)//2.
# The heap invariant: every parent is <= its children, so the min is at index 0.
class MinHeap:
def __init__(self):
self.data = []
def push(self, x):
# Append at the end — that keeps the tree "complete", but may break the
# invariant, since the new leaf could be smaller than its parent.
self.data.append(x)# A binary heap is stored in a flat list. For the node at index i:
# left child = 2i+1, right child = 2i+2, parent = (i-1)//2.
# The heap invariant: every parent is <= its children, so the min is at index 0.
class MinHeap:
def __init__(self):
self.data = []
def push(self, x):
# Append at the end — that keeps the tree "complete", but may break the
# invariant, since the new leaf could be smaller than its parent.
self.data.append(x)
# Bubble the newcomer up until it's >= its parent again.# A binary heap is stored in a flat list. For the node at index i:
# left child = 2i+1, right child = 2i+2, parent = (i-1)//2.
# The heap invariant: every parent is <= its children, so the min is at index 0.
class MinHeap:
def __init__(self):
self.data = []
def push(self, x):
# Append at the end — that keeps the tree "complete", but may break the
# invariant, since the new leaf could be smaller than its parent.
self.data.append(x)
# Bubble the newcomer up until it's >= its parent again.
self._up(len(self.data) - 1)# A binary heap is stored in a flat list. For the node at index i:
# left child = 2i+1, right child = 2i+2, parent = (i-1)//2.
# The heap invariant: every parent is <= its children, so the min is at index 0.
class MinHeap:
def __init__(self):
self.data = []
def push(self, x):
# Append at the end — that keeps the tree "complete", but may break the
# invariant, since the new leaf could be smaller than its parent.
self.data.append(x)
# Bubble the newcomer up until it's >= its parent again.
self._up(len(self.data) - 1)
# The min lives at the root. Swap it with the last leaf so we can remove it
# from the end cheaply.# A binary heap is stored in a flat list. For the node at index i:
# left child = 2i+1, right child = 2i+2, parent = (i-1)//2.
# The heap invariant: every parent is <= its children, so the min is at index 0.
class MinHeap:
def __init__(self):
self.data = []
def push(self, x):
# Append at the end — that keeps the tree "complete", but may break the
# invariant, since the new leaf could be smaller than its parent.
self.data.append(x)
# Bubble the newcomer up until it's >= its parent again.
self._up(len(self.data) - 1)
def pop(self):
# The min lives at the root. Swap it with the last leaf so we can remove it
# from the end cheaply.
n = len(self.data) - 1
self.data[0], self.data[n] = self.data[n], self.data[0]
min_val = self.data[n]# A binary heap is stored in a flat list. For the node at index i:
# left child = 2i+1, right child = 2i+2, parent = (i-1)//2.
# The heap invariant: every parent is <= its children, so the min is at index 0.
class MinHeap:
def __init__(self):
self.data = []
def push(self, x):
# Append at the end — that keeps the tree "complete", but may break the
# invariant, since the new leaf could be smaller than its parent.
self.data.append(x)
# Bubble the newcomer up until it's >= its parent again.
self._up(len(self.data) - 1)
def pop(self):
# The min lives at the root. Swap it with the last leaf so we can remove it
# from the end cheaply.
n = len(self.data) - 1
self.data[0], self.data[n] = self.data[n], self.data[0]
min_val = self.data[n]
# Drop the old min, then sift the leaf that's now at the root back down.# A binary heap is stored in a flat list. For the node at index i:
# left child = 2i+1, right child = 2i+2, parent = (i-1)//2.
# The heap invariant: every parent is <= its children, so the min is at index 0.
class MinHeap:
def __init__(self):
self.data = []
def push(self, x):
# Append at the end — that keeps the tree "complete", but may break the
# invariant, since the new leaf could be smaller than its parent.
self.data.append(x)
# Bubble the newcomer up until it's >= its parent again.
self._up(len(self.data) - 1)
def pop(self):
# The min lives at the root. Swap it with the last leaf so we can remove it
# from the end cheaply.
n = len(self.data) - 1
self.data[0], self.data[n] = self.data[n], self.data[0]
min_val = self.data[n]
# Drop the old min, then sift the leaf that's now at the root back down.
self.data.pop()
self._down(0)
return min_val# A binary heap is stored in a flat list. For the node at index i:
# left child = 2i+1, right child = 2i+2, parent = (i-1)//2.
# The heap invariant: every parent is <= its children, so the min is at index 0.
class MinHeap:
def __init__(self):
self.data = []
def push(self, x):
# Append at the end — that keeps the tree "complete", but may break the
# invariant, since the new leaf could be smaller than its parent.
self.data.append(x)
# Bubble the newcomer up until it's >= its parent again.
self._up(len(self.data) - 1)
def pop(self):
# The min lives at the root. Swap it with the last leaf so we can remove it
# from the end cheaply.
n = len(self.data) - 1
self.data[0], self.data[n] = self.data[n], self.data[0]
min_val = self.data[n]
# Drop the old min, then sift the leaf that's now at the root back down.
self.data.pop()
self._down(0)
return min_val
# _up: while a node is smaller than its parent, swap them and follow it upward.# A binary heap is stored in a flat list. For the node at index i:
# left child = 2i+1, right child = 2i+2, parent = (i-1)//2.
# The heap invariant: every parent is <= its children, so the min is at index 0.
class MinHeap:
def __init__(self):
self.data = []
def push(self, x):
# Append at the end — that keeps the tree "complete", but may break the
# invariant, since the new leaf could be smaller than its parent.
self.data.append(x)
# Bubble the newcomer up until it's >= its parent again.
self._up(len(self.data) - 1)
def pop(self):
# The min lives at the root. Swap it with the last leaf so we can remove it
# from the end cheaply.
n = len(self.data) - 1
self.data[0], self.data[n] = self.data[n], self.data[0]
min_val = self.data[n]
# Drop the old min, then sift the leaf that's now at the root back down.
self.data.pop()
self._down(0)
return min_val
# _up: while a node is smaller than its parent, swap them and follow it upward.
def _up(self, i):
while i > 0:
parent = (i - 1) // 2
if self.data[parent] <= self.data[i]:
break # parent already <= node: invariant restored
self.data[parent], self.data[i] = self.data[i], self.data[parent]
i = parent# A binary heap is stored in a flat list. For the node at index i:
# left child = 2i+1, right child = 2i+2, parent = (i-1)//2.
# The heap invariant: every parent is <= its children, so the min is at index 0.
class MinHeap:
def __init__(self):
self.data = []
def push(self, x):
# Append at the end — that keeps the tree "complete", but may break the
# invariant, since the new leaf could be smaller than its parent.
self.data.append(x)
# Bubble the newcomer up until it's >= its parent again.
self._up(len(self.data) - 1)
def pop(self):
# The min lives at the root. Swap it with the last leaf so we can remove it
# from the end cheaply.
n = len(self.data) - 1
self.data[0], self.data[n] = self.data[n], self.data[0]
min_val = self.data[n]
# Drop the old min, then sift the leaf that's now at the root back down.
self.data.pop()
self._down(0)
return min_val
# _up: while a node is smaller than its parent, swap them and follow it upward.
def _up(self, i):
while i > 0:
parent = (i - 1) // 2
if self.data[parent] <= self.data[i]:
break # parent already <= node: invariant restored
self.data[parent], self.data[i] = self.data[i], self.data[parent]
i = parent
# _down: repeatedly swap a node with its SMALLEST child until it sits above both.
# Assume i is smallest, then check its two children.# A binary heap is stored in a flat list. For the node at index i:
# left child = 2i+1, right child = 2i+2, parent = (i-1)//2.
# The heap invariant: every parent is <= its children, so the min is at index 0.
class MinHeap:
def __init__(self):
self.data = []
def push(self, x):
# Append at the end — that keeps the tree "complete", but may break the
# invariant, since the new leaf could be smaller than its parent.
self.data.append(x)
# Bubble the newcomer up until it's >= its parent again.
self._up(len(self.data) - 1)
def pop(self):
# The min lives at the root. Swap it with the last leaf so we can remove it
# from the end cheaply.
n = len(self.data) - 1
self.data[0], self.data[n] = self.data[n], self.data[0]
min_val = self.data[n]
# Drop the old min, then sift the leaf that's now at the root back down.
self.data.pop()
self._down(0)
return min_val
# _up: while a node is smaller than its parent, swap them and follow it upward.
def _up(self, i):
while i > 0:
parent = (i - 1) // 2
if self.data[parent] <= self.data[i]:
break # parent already <= node: invariant restored
self.data[parent], self.data[i] = self.data[i], self.data[parent]
i = parent
# _down: repeatedly swap a node with its SMALLEST child until it sits above both.
def _down(self, i):
n = len(self.data)
while True:
# Assume i is smallest, then check its two children.
smallest, l, r = i, 2 * i + 1, 2 * i + 2
if l < n and self.data[l] < self.data[smallest]:
smallest = l
if r < n and self.data[r] < self.data[smallest]:
smallest = r
if smallest == i:
break # node is already <= both children
self.data[i], self.data[smallest] = self.data[smallest], self.data[i]
i = smallest// A binary heap is stored in a flat array. For the node at index i:
// left child = 2i+1, right child = 2i+2, parent = floor((i-1)/2).
// The heap invariant: every parent is <= its children, so the min is at index 0.
class MinHeap {
constructor() {
this.data = [];
}
}// A binary heap is stored in a flat array. For the node at index i:
// left child = 2i+1, right child = 2i+2, parent = floor((i-1)/2).
// The heap invariant: every parent is <= its children, so the min is at index 0.
class MinHeap {
constructor() {
this.data = [];
}
// Append at the end — that keeps the tree "complete", but may break the
// invariant, since the new leaf could be smaller than its parent.
}// A binary heap is stored in a flat array. For the node at index i:
// left child = 2i+1, right child = 2i+2, parent = floor((i-1)/2).
// The heap invariant: every parent is <= its children, so the min is at index 0.
class MinHeap {
constructor() {
this.data = [];
}
push(x) {
// Append at the end — that keeps the tree "complete", but may break the
// invariant, since the new leaf could be smaller than its parent.
this.data.push(x);
}
}// A binary heap is stored in a flat array. For the node at index i:
// left child = 2i+1, right child = 2i+2, parent = floor((i-1)/2).
// The heap invariant: every parent is <= its children, so the min is at index 0.
class MinHeap {
constructor() {
this.data = [];
}
push(x) {
// Append at the end — that keeps the tree "complete", but may break the
// invariant, since the new leaf could be smaller than its parent.
this.data.push(x);
// Bubble the newcomer up until it's >= its parent again.
}
}// A binary heap is stored in a flat array. For the node at index i:
// left child = 2i+1, right child = 2i+2, parent = floor((i-1)/2).
// The heap invariant: every parent is <= its children, so the min is at index 0.
class MinHeap {
constructor() {
this.data = [];
}
push(x) {
// Append at the end — that keeps the tree "complete", but may break the
// invariant, since the new leaf could be smaller than its parent.
this.data.push(x);
// Bubble the newcomer up until it's >= its parent again.
this.up(this.data.length - 1);
}
}// A binary heap is stored in a flat array. For the node at index i:
// left child = 2i+1, right child = 2i+2, parent = floor((i-1)/2).
// The heap invariant: every parent is <= its children, so the min is at index 0.
class MinHeap {
constructor() {
this.data = [];
}
push(x) {
// Append at the end — that keeps the tree "complete", but may break the
// invariant, since the new leaf could be smaller than its parent.
this.data.push(x);
// Bubble the newcomer up until it's >= its parent again.
this.up(this.data.length - 1);
}
// The min lives at the root. Swap it with the last leaf so we can remove it
// from the end cheaply.
}// A binary heap is stored in a flat array. For the node at index i:
// left child = 2i+1, right child = 2i+2, parent = floor((i-1)/2).
// The heap invariant: every parent is <= its children, so the min is at index 0.
class MinHeap {
constructor() {
this.data = [];
}
push(x) {
// Append at the end — that keeps the tree "complete", but may break the
// invariant, since the new leaf could be smaller than its parent.
this.data.push(x);
// Bubble the newcomer up until it's >= its parent again.
this.up(this.data.length - 1);
}
pop() {
// The min lives at the root. Swap it with the last leaf so we can remove it
// from the end cheaply.
const n = this.data.length - 1;
[this.data[0], this.data[n]] = [this.data[n], this.data[0]];
const min = this.data[n];
}
}// A binary heap is stored in a flat array. For the node at index i:
// left child = 2i+1, right child = 2i+2, parent = floor((i-1)/2).
// The heap invariant: every parent is <= its children, so the min is at index 0.
class MinHeap {
constructor() {
this.data = [];
}
push(x) {
// Append at the end — that keeps the tree "complete", but may break the
// invariant, since the new leaf could be smaller than its parent.
this.data.push(x);
// Bubble the newcomer up until it's >= its parent again.
this.up(this.data.length - 1);
}
pop() {
// The min lives at the root. Swap it with the last leaf so we can remove it
// from the end cheaply.
const n = this.data.length - 1;
[this.data[0], this.data[n]] = [this.data[n], this.data[0]];
const min = this.data[n];
// Drop the old min, then sift the leaf that's now at the root back down.
}
}// A binary heap is stored in a flat array. For the node at index i:
// left child = 2i+1, right child = 2i+2, parent = floor((i-1)/2).
// The heap invariant: every parent is <= its children, so the min is at index 0.
class MinHeap {
constructor() {
this.data = [];
}
push(x) {
// Append at the end — that keeps the tree "complete", but may break the
// invariant, since the new leaf could be smaller than its parent.
this.data.push(x);
// Bubble the newcomer up until it's >= its parent again.
this.up(this.data.length - 1);
}
pop() {
// The min lives at the root. Swap it with the last leaf so we can remove it
// from the end cheaply.
const n = this.data.length - 1;
[this.data[0], this.data[n]] = [this.data[n], this.data[0]];
const min = this.data[n];
// Drop the old min, then sift the leaf that's now at the root back down.
this.data.pop();
this.down(0);
return min;
}
}// A binary heap is stored in a flat array. For the node at index i:
// left child = 2i+1, right child = 2i+2, parent = floor((i-1)/2).
// The heap invariant: every parent is <= its children, so the min is at index 0.
class MinHeap {
constructor() {
this.data = [];
}
push(x) {
// Append at the end — that keeps the tree "complete", but may break the
// invariant, since the new leaf could be smaller than its parent.
this.data.push(x);
// Bubble the newcomer up until it's >= its parent again.
this.up(this.data.length - 1);
}
pop() {
// The min lives at the root. Swap it with the last leaf so we can remove it
// from the end cheaply.
const n = this.data.length - 1;
[this.data[0], this.data[n]] = [this.data[n], this.data[0]];
const min = this.data[n];
// Drop the old min, then sift the leaf that's now at the root back down.
this.data.pop();
this.down(0);
return min;
}
// up: while a node is smaller than its parent, swap them and follow it upward.
}// A binary heap is stored in a flat array. For the node at index i:
// left child = 2i+1, right child = 2i+2, parent = floor((i-1)/2).
// The heap invariant: every parent is <= its children, so the min is at index 0.
class MinHeap {
constructor() {
this.data = [];
}
push(x) {
// Append at the end — that keeps the tree "complete", but may break the
// invariant, since the new leaf could be smaller than its parent.
this.data.push(x);
// Bubble the newcomer up until it's >= its parent again.
this.up(this.data.length - 1);
}
pop() {
// The min lives at the root. Swap it with the last leaf so we can remove it
// from the end cheaply.
const n = this.data.length - 1;
[this.data[0], this.data[n]] = [this.data[n], this.data[0]];
const min = this.data[n];
// Drop the old min, then sift the leaf that's now at the root back down.
this.data.pop();
this.down(0);
return min;
}
// up: while a node is smaller than its parent, swap them and follow it upward.
up(i) {
while (i > 0) {
const parent = Math.floor((i - 1) / 2);
if (this.data[parent] <= this.data[i]) {
break; // parent already <= node: invariant restored
}
[this.data[parent], this.data[i]] = [this.data[i], this.data[parent]];
i = parent;
}
}
}// A binary heap is stored in a flat array. For the node at index i:
// left child = 2i+1, right child = 2i+2, parent = floor((i-1)/2).
// The heap invariant: every parent is <= its children, so the min is at index 0.
class MinHeap {
constructor() {
this.data = [];
}
push(x) {
// Append at the end — that keeps the tree "complete", but may break the
// invariant, since the new leaf could be smaller than its parent.
this.data.push(x);
// Bubble the newcomer up until it's >= its parent again.
this.up(this.data.length - 1);
}
pop() {
// The min lives at the root. Swap it with the last leaf so we can remove it
// from the end cheaply.
const n = this.data.length - 1;
[this.data[0], this.data[n]] = [this.data[n], this.data[0]];
const min = this.data[n];
// Drop the old min, then sift the leaf that's now at the root back down.
this.data.pop();
this.down(0);
return min;
}
// up: while a node is smaller than its parent, swap them and follow it upward.
up(i) {
while (i > 0) {
const parent = Math.floor((i - 1) / 2);
if (this.data[parent] <= this.data[i]) {
break; // parent already <= node: invariant restored
}
[this.data[parent], this.data[i]] = [this.data[i], this.data[parent]];
i = parent;
}
}
// down: repeatedly swap a node with its SMALLEST child until it sits above both.
// Assume i is smallest, then check its two children.
}// A binary heap is stored in a flat array. For the node at index i:
// left child = 2i+1, right child = 2i+2, parent = floor((i-1)/2).
// The heap invariant: every parent is <= its children, so the min is at index 0.
class MinHeap {
constructor() {
this.data = [];
}
push(x) {
// Append at the end — that keeps the tree "complete", but may break the
// invariant, since the new leaf could be smaller than its parent.
this.data.push(x);
// Bubble the newcomer up until it's >= its parent again.
this.up(this.data.length - 1);
}
pop() {
// The min lives at the root. Swap it with the last leaf so we can remove it
// from the end cheaply.
const n = this.data.length - 1;
[this.data[0], this.data[n]] = [this.data[n], this.data[0]];
const min = this.data[n];
// Drop the old min, then sift the leaf that's now at the root back down.
this.data.pop();
this.down(0);
return min;
}
// up: while a node is smaller than its parent, swap them and follow it upward.
up(i) {
while (i > 0) {
const parent = Math.floor((i - 1) / 2);
if (this.data[parent] <= this.data[i]) {
break; // parent already <= node: invariant restored
}
[this.data[parent], this.data[i]] = [this.data[i], this.data[parent]];
i = parent;
}
}
// down: repeatedly swap a node with its SMALLEST child until it sits above both.
down(i) {
const n = this.data.length;
for (;;) {
// Assume i is smallest, then check its two children.
let smallest = i;
const l = 2 * i + 1, r = 2 * i + 2;
if (l < n && this.data[l] < this.data[smallest]) {
smallest = l;
}
if (r < n && this.data[r] < this.data[smallest]) {
smallest = r;
}
if (smallest === i) {
break; // node is already <= both children
}
[this.data[i], this.data[smallest]] = [this.data[smallest], this.data[i]];
i = smallest;
}
}
}// A binary heap is stored in a flat array. For the node at index i:
// left child = 2i+1, right child = 2i+2, parent = floor((i-1)/2).
// The heap invariant: every parent is <= its children, so the min is at index 0.
class MinHeap {
private data: number[];
constructor() {
this.data = [];
}
}// A binary heap is stored in a flat array. For the node at index i:
// left child = 2i+1, right child = 2i+2, parent = floor((i-1)/2).
// The heap invariant: every parent is <= its children, so the min is at index 0.
class MinHeap {
private data: number[];
constructor() {
this.data = [];
}
// Append at the end — that keeps the tree "complete", but may break the
// invariant, since the new leaf could be smaller than its parent.
}// A binary heap is stored in a flat array. For the node at index i:
// left child = 2i+1, right child = 2i+2, parent = floor((i-1)/2).
// The heap invariant: every parent is <= its children, so the min is at index 0.
class MinHeap {
private data: number[];
constructor() {
this.data = [];
}
push(x: number): void {
// Append at the end — that keeps the tree "complete", but may break the
// invariant, since the new leaf could be smaller than its parent.
this.data.push(x);
}
}// A binary heap is stored in a flat array. For the node at index i:
// left child = 2i+1, right child = 2i+2, parent = floor((i-1)/2).
// The heap invariant: every parent is <= its children, so the min is at index 0.
class MinHeap {
private data: number[];
constructor() {
this.data = [];
}
push(x: number): void {
// Append at the end — that keeps the tree "complete", but may break the
// invariant, since the new leaf could be smaller than its parent.
this.data.push(x);
// Bubble the newcomer up until it's >= its parent again.
}
}// A binary heap is stored in a flat array. For the node at index i:
// left child = 2i+1, right child = 2i+2, parent = floor((i-1)/2).
// The heap invariant: every parent is <= its children, so the min is at index 0.
class MinHeap {
private data: number[];
constructor() {
this.data = [];
}
push(x: number): void {
// Append at the end — that keeps the tree "complete", but may break the
// invariant, since the new leaf could be smaller than its parent.
this.data.push(x);
// Bubble the newcomer up until it's >= its parent again.
this.up(this.data.length - 1);
}
}// A binary heap is stored in a flat array. For the node at index i:
// left child = 2i+1, right child = 2i+2, parent = floor((i-1)/2).
// The heap invariant: every parent is <= its children, so the min is at index 0.
class MinHeap {
private data: number[];
constructor() {
this.data = [];
}
push(x: number): void {
// Append at the end — that keeps the tree "complete", but may break the
// invariant, since the new leaf could be smaller than its parent.
this.data.push(x);
// Bubble the newcomer up until it's >= its parent again.
this.up(this.data.length - 1);
}
// The min lives at the root. Swap it with the last leaf so we can remove it
// from the end cheaply.
}// A binary heap is stored in a flat array. For the node at index i:
// left child = 2i+1, right child = 2i+2, parent = floor((i-1)/2).
// The heap invariant: every parent is <= its children, so the min is at index 0.
class MinHeap {
private data: number[];
constructor() {
this.data = [];
}
push(x: number): void {
// Append at the end — that keeps the tree "complete", but may break the
// invariant, since the new leaf could be smaller than its parent.
this.data.push(x);
// Bubble the newcomer up until it's >= its parent again.
this.up(this.data.length - 1);
}
pop(): number {
// The min lives at the root. Swap it with the last leaf so we can remove it
// from the end cheaply.
const n = this.data.length - 1;
[this.data[0], this.data[n]] = [this.data[n], this.data[0]];
const min = this.data[n];
}
}// A binary heap is stored in a flat array. For the node at index i:
// left child = 2i+1, right child = 2i+2, parent = floor((i-1)/2).
// The heap invariant: every parent is <= its children, so the min is at index 0.
class MinHeap {
private data: number[];
constructor() {
this.data = [];
}
push(x: number): void {
// Append at the end — that keeps the tree "complete", but may break the
// invariant, since the new leaf could be smaller than its parent.
this.data.push(x);
// Bubble the newcomer up until it's >= its parent again.
this.up(this.data.length - 1);
}
pop(): number {
// The min lives at the root. Swap it with the last leaf so we can remove it
// from the end cheaply.
const n = this.data.length - 1;
[this.data[0], this.data[n]] = [this.data[n], this.data[0]];
const min = this.data[n];
// Drop the old min, then sift the leaf that's now at the root back down.
}
}// A binary heap is stored in a flat array. For the node at index i:
// left child = 2i+1, right child = 2i+2, parent = floor((i-1)/2).
// The heap invariant: every parent is <= its children, so the min is at index 0.
class MinHeap {
private data: number[];
constructor() {
this.data = [];
}
push(x: number): void {
// Append at the end — that keeps the tree "complete", but may break the
// invariant, since the new leaf could be smaller than its parent.
this.data.push(x);
// Bubble the newcomer up until it's >= its parent again.
this.up(this.data.length - 1);
}
pop(): number {
// The min lives at the root. Swap it with the last leaf so we can remove it
// from the end cheaply.
const n = this.data.length - 1;
[this.data[0], this.data[n]] = [this.data[n], this.data[0]];
const min = this.data[n];
// Drop the old min, then sift the leaf that's now at the root back down.
this.data.pop();
this.down(0);
return min;
}
}// A binary heap is stored in a flat array. For the node at index i:
// left child = 2i+1, right child = 2i+2, parent = floor((i-1)/2).
// The heap invariant: every parent is <= its children, so the min is at index 0.
class MinHeap {
private data: number[];
constructor() {
this.data = [];
}
push(x: number): void {
// Append at the end — that keeps the tree "complete", but may break the
// invariant, since the new leaf could be smaller than its parent.
this.data.push(x);
// Bubble the newcomer up until it's >= its parent again.
this.up(this.data.length - 1);
}
pop(): number {
// The min lives at the root. Swap it with the last leaf so we can remove it
// from the end cheaply.
const n = this.data.length - 1;
[this.data[0], this.data[n]] = [this.data[n], this.data[0]];
const min = this.data[n];
// Drop the old min, then sift the leaf that's now at the root back down.
this.data.pop();
this.down(0);
return min;
}
// up: while a node is smaller than its parent, swap them and follow it upward.
}// A binary heap is stored in a flat array. For the node at index i:
// left child = 2i+1, right child = 2i+2, parent = floor((i-1)/2).
// The heap invariant: every parent is <= its children, so the min is at index 0.
class MinHeap {
private data: number[];
constructor() {
this.data = [];
}
push(x: number): void {
// Append at the end — that keeps the tree "complete", but may break the
// invariant, since the new leaf could be smaller than its parent.
this.data.push(x);
// Bubble the newcomer up until it's >= its parent again.
this.up(this.data.length - 1);
}
pop(): number {
// The min lives at the root. Swap it with the last leaf so we can remove it
// from the end cheaply.
const n = this.data.length - 1;
[this.data[0], this.data[n]] = [this.data[n], this.data[0]];
const min = this.data[n];
// Drop the old min, then sift the leaf that's now at the root back down.
this.data.pop();
this.down(0);
return min;
}
// up: while a node is smaller than its parent, swap them and follow it upward.
private up(i: number): void {
while (i > 0) {
const parent = Math.floor((i - 1) / 2);
if (this.data[parent] <= this.data[i]) {
break; // parent already <= node: invariant restored
}
[this.data[parent], this.data[i]] = [this.data[i], this.data[parent]];
i = parent;
}
}
}// A binary heap is stored in a flat array. For the node at index i:
// left child = 2i+1, right child = 2i+2, parent = floor((i-1)/2).
// The heap invariant: every parent is <= its children, so the min is at index 0.
class MinHeap {
private data: number[];
constructor() {
this.data = [];
}
push(x: number): void {
// Append at the end — that keeps the tree "complete", but may break the
// invariant, since the new leaf could be smaller than its parent.
this.data.push(x);
// Bubble the newcomer up until it's >= its parent again.
this.up(this.data.length - 1);
}
pop(): number {
// The min lives at the root. Swap it with the last leaf so we can remove it
// from the end cheaply.
const n = this.data.length - 1;
[this.data[0], this.data[n]] = [this.data[n], this.data[0]];
const min = this.data[n];
// Drop the old min, then sift the leaf that's now at the root back down.
this.data.pop();
this.down(0);
return min;
}
// up: while a node is smaller than its parent, swap them and follow it upward.
private up(i: number): void {
while (i > 0) {
const parent = Math.floor((i - 1) / 2);
if (this.data[parent] <= this.data[i]) {
break; // parent already <= node: invariant restored
}
[this.data[parent], this.data[i]] = [this.data[i], this.data[parent]];
i = parent;
}
}
// down: repeatedly swap a node with its SMALLEST child until it sits above both.
// Assume i is smallest, then check its two children.
}// A binary heap is stored in a flat array. For the node at index i:
// left child = 2i+1, right child = 2i+2, parent = floor((i-1)/2).
// The heap invariant: every parent is <= its children, so the min is at index 0.
class MinHeap {
private data: number[];
constructor() {
this.data = [];
}
push(x: number): void {
// Append at the end — that keeps the tree "complete", but may break the
// invariant, since the new leaf could be smaller than its parent.
this.data.push(x);
// Bubble the newcomer up until it's >= its parent again.
this.up(this.data.length - 1);
}
pop(): number {
// The min lives at the root. Swap it with the last leaf so we can remove it
// from the end cheaply.
const n = this.data.length - 1;
[this.data[0], this.data[n]] = [this.data[n], this.data[0]];
const min = this.data[n];
// Drop the old min, then sift the leaf that's now at the root back down.
this.data.pop();
this.down(0);
return min;
}
// up: while a node is smaller than its parent, swap them and follow it upward.
private up(i: number): void {
while (i > 0) {
const parent = Math.floor((i - 1) / 2);
if (this.data[parent] <= this.data[i]) {
break; // parent already <= node: invariant restored
}
[this.data[parent], this.data[i]] = [this.data[i], this.data[parent]];
i = parent;
}
}
// down: repeatedly swap a node with its SMALLEST child until it sits above both.
private down(i: number): void {
const n = this.data.length;
for (;;) {
// Assume i is smallest, then check its two children.
let smallest = i;
const l = 2 * i + 1, r = 2 * i + 2;
if (l < n && this.data[l] < this.data[smallest]) {
smallest = l;
}
if (r < n && this.data[r] < this.data[smallest]) {
smallest = r;
}
if (smallest === i) {
break; // node is already <= both children
}
[this.data[i], this.data[smallest]] = [this.data[smallest], this.data[i]];
i = smallest;
}
}
}import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
// A binary heap is stored in a flat list. For the node at index i:
// left child = 2i+1, right child = 2i+2, parent = (i-1)/2.
// The heap invariant: every parent is <= its children, so the min is at index 0.
class MinHeap {
private final List<Integer> data = new ArrayList<>();
}import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
// A binary heap is stored in a flat list. For the node at index i:
// left child = 2i+1, right child = 2i+2, parent = (i-1)/2.
// The heap invariant: every parent is <= its children, so the min is at index 0.
class MinHeap {
private final List<Integer> data = new ArrayList<>();
// Append at the end — that keeps the tree "complete", but may break the
// invariant, since the new leaf could be smaller than its parent.
}import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
// A binary heap is stored in a flat list. For the node at index i:
// left child = 2i+1, right child = 2i+2, parent = (i-1)/2.
// The heap invariant: every parent is <= its children, so the min is at index 0.
class MinHeap {
private final List<Integer> data = new ArrayList<>();
void push(int x) {
// Append at the end — that keeps the tree "complete", but may break the
// invariant, since the new leaf could be smaller than its parent.
data.add(x);
}
}import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
// A binary heap is stored in a flat list. For the node at index i:
// left child = 2i+1, right child = 2i+2, parent = (i-1)/2.
// The heap invariant: every parent is <= its children, so the min is at index 0.
class MinHeap {
private final List<Integer> data = new ArrayList<>();
void push(int x) {
// Append at the end — that keeps the tree "complete", but may break the
// invariant, since the new leaf could be smaller than its parent.
data.add(x);
// Bubble the newcomer up until it's >= its parent again.
}
}import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
// A binary heap is stored in a flat list. For the node at index i:
// left child = 2i+1, right child = 2i+2, parent = (i-1)/2.
// The heap invariant: every parent is <= its children, so the min is at index 0.
class MinHeap {
private final List<Integer> data = new ArrayList<>();
void push(int x) {
// Append at the end — that keeps the tree "complete", but may break the
// invariant, since the new leaf could be smaller than its parent.
data.add(x);
// Bubble the newcomer up until it's >= its parent again.
up(data.size() - 1);
}
}import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
// A binary heap is stored in a flat list. For the node at index i:
// left child = 2i+1, right child = 2i+2, parent = (i-1)/2.
// The heap invariant: every parent is <= its children, so the min is at index 0.
class MinHeap {
private final List<Integer> data = new ArrayList<>();
void push(int x) {
// Append at the end — that keeps the tree "complete", but may break the
// invariant, since the new leaf could be smaller than its parent.
data.add(x);
// Bubble the newcomer up until it's >= its parent again.
up(data.size() - 1);
}
// The min lives at the root. Swap it with the last leaf so we can remove it
// from the end cheaply.
}import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
// A binary heap is stored in a flat list. For the node at index i:
// left child = 2i+1, right child = 2i+2, parent = (i-1)/2.
// The heap invariant: every parent is <= its children, so the min is at index 0.
class MinHeap {
private final List<Integer> data = new ArrayList<>();
void push(int x) {
// Append at the end — that keeps the tree "complete", but may break the
// invariant, since the new leaf could be smaller than its parent.
data.add(x);
// Bubble the newcomer up until it's >= its parent again.
up(data.size() - 1);
}
int pop() {
// The min lives at the root. Swap it with the last leaf so we can remove it
// from the end cheaply.
int n = data.size() - 1;
Collections.swap(data, 0, n);
int min = data.get(n);
}
}import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
// A binary heap is stored in a flat list. For the node at index i:
// left child = 2i+1, right child = 2i+2, parent = (i-1)/2.
// The heap invariant: every parent is <= its children, so the min is at index 0.
class MinHeap {
private final List<Integer> data = new ArrayList<>();
void push(int x) {
// Append at the end — that keeps the tree "complete", but may break the
// invariant, since the new leaf could be smaller than its parent.
data.add(x);
// Bubble the newcomer up until it's >= its parent again.
up(data.size() - 1);
}
int pop() {
// The min lives at the root. Swap it with the last leaf so we can remove it
// from the end cheaply.
int n = data.size() - 1;
Collections.swap(data, 0, n);
int min = data.get(n);
// Drop the old min, then sift the leaf that's now at the root back down.
}
}import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
// A binary heap is stored in a flat list. For the node at index i:
// left child = 2i+1, right child = 2i+2, parent = (i-1)/2.
// The heap invariant: every parent is <= its children, so the min is at index 0.
class MinHeap {
private final List<Integer> data = new ArrayList<>();
void push(int x) {
// Append at the end — that keeps the tree "complete", but may break the
// invariant, since the new leaf could be smaller than its parent.
data.add(x);
// Bubble the newcomer up until it's >= its parent again.
up(data.size() - 1);
}
int pop() {
// The min lives at the root. Swap it with the last leaf so we can remove it
// from the end cheaply.
int n = data.size() - 1;
Collections.swap(data, 0, n);
int min = data.get(n);
// Drop the old min, then sift the leaf that's now at the root back down.
data.remove(n);
down(0);
return min;
}
}import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
// A binary heap is stored in a flat list. For the node at index i:
// left child = 2i+1, right child = 2i+2, parent = (i-1)/2.
// The heap invariant: every parent is <= its children, so the min is at index 0.
class MinHeap {
private final List<Integer> data = new ArrayList<>();
void push(int x) {
// Append at the end — that keeps the tree "complete", but may break the
// invariant, since the new leaf could be smaller than its parent.
data.add(x);
// Bubble the newcomer up until it's >= its parent again.
up(data.size() - 1);
}
int pop() {
// The min lives at the root. Swap it with the last leaf so we can remove it
// from the end cheaply.
int n = data.size() - 1;
Collections.swap(data, 0, n);
int min = data.get(n);
// Drop the old min, then sift the leaf that's now at the root back down.
data.remove(n);
down(0);
return min;
}
// up: while a node is smaller than its parent, swap them and follow it upward.
}import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
// A binary heap is stored in a flat list. For the node at index i:
// left child = 2i+1, right child = 2i+2, parent = (i-1)/2.
// The heap invariant: every parent is <= its children, so the min is at index 0.
class MinHeap {
private final List<Integer> data = new ArrayList<>();
void push(int x) {
// Append at the end — that keeps the tree "complete", but may break the
// invariant, since the new leaf could be smaller than its parent.
data.add(x);
// Bubble the newcomer up until it's >= its parent again.
up(data.size() - 1);
}
int pop() {
// The min lives at the root. Swap it with the last leaf so we can remove it
// from the end cheaply.
int n = data.size() - 1;
Collections.swap(data, 0, n);
int min = data.get(n);
// Drop the old min, then sift the leaf that's now at the root back down.
data.remove(n);
down(0);
return min;
}
// up: while a node is smaller than its parent, swap them and follow it upward.
private void up(int i) {
while (i > 0) {
int parent = (i - 1) / 2;
if (data.get(parent) <= data.get(i)) {
break; // parent already <= node: invariant restored
}
Collections.swap(data, parent, i);
i = parent;
}
}
}import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
// A binary heap is stored in a flat list. For the node at index i:
// left child = 2i+1, right child = 2i+2, parent = (i-1)/2.
// The heap invariant: every parent is <= its children, so the min is at index 0.
class MinHeap {
private final List<Integer> data = new ArrayList<>();
void push(int x) {
// Append at the end — that keeps the tree "complete", but may break the
// invariant, since the new leaf could be smaller than its parent.
data.add(x);
// Bubble the newcomer up until it's >= its parent again.
up(data.size() - 1);
}
int pop() {
// The min lives at the root. Swap it with the last leaf so we can remove it
// from the end cheaply.
int n = data.size() - 1;
Collections.swap(data, 0, n);
int min = data.get(n);
// Drop the old min, then sift the leaf that's now at the root back down.
data.remove(n);
down(0);
return min;
}
// up: while a node is smaller than its parent, swap them and follow it upward.
private void up(int i) {
while (i > 0) {
int parent = (i - 1) / 2;
if (data.get(parent) <= data.get(i)) {
break; // parent already <= node: invariant restored
}
Collections.swap(data, parent, i);
i = parent;
}
}
// down: repeatedly swap a node with its SMALLEST child until it sits above both.
// Assume i is smallest, then check its two children.
}import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
// A binary heap is stored in a flat list. For the node at index i:
// left child = 2i+1, right child = 2i+2, parent = (i-1)/2.
// The heap invariant: every parent is <= its children, so the min is at index 0.
class MinHeap {
private final List<Integer> data = new ArrayList<>();
void push(int x) {
// Append at the end — that keeps the tree "complete", but may break the
// invariant, since the new leaf could be smaller than its parent.
data.add(x);
// Bubble the newcomer up until it's >= its parent again.
up(data.size() - 1);
}
int pop() {
// The min lives at the root. Swap it with the last leaf so we can remove it
// from the end cheaply.
int n = data.size() - 1;
Collections.swap(data, 0, n);
int min = data.get(n);
// Drop the old min, then sift the leaf that's now at the root back down.
data.remove(n);
down(0);
return min;
}
// up: while a node is smaller than its parent, swap them and follow it upward.
private void up(int i) {
while (i > 0) {
int parent = (i - 1) / 2;
if (data.get(parent) <= data.get(i)) {
break; // parent already <= node: invariant restored
}
Collections.swap(data, parent, i);
i = parent;
}
}
// down: repeatedly swap a node with its SMALLEST child until it sits above both.
private void down(int i) {
int n = data.size();
while (true) {
// Assume i is smallest, then check its two children.
int smallest = i, l = 2 * i + 1, r = 2 * i + 2;
if (l < n && data.get(l) < data.get(smallest)) {
smallest = l;
}
if (r < n && data.get(r) < data.get(smallest)) {
smallest = r;
}
if (smallest == i) {
break; // node is already <= both children
}
Collections.swap(data, i, smallest);
i = smallest;
}
}
}using System.Collections.Generic;
// A binary heap is stored in a flat list. For the node at index i:
// left child = 2i+1, right child = 2i+2, parent = (i-1)/2.
// The heap invariant: every parent is <= its children, so the min is at index 0.
public class MinHeap {
private readonly List<int> data = new List<int>();
}using System.Collections.Generic;
// A binary heap is stored in a flat list. For the node at index i:
// left child = 2i+1, right child = 2i+2, parent = (i-1)/2.
// The heap invariant: every parent is <= its children, so the min is at index 0.
public class MinHeap {
private readonly List<int> data = new List<int>();
// Append at the end — that keeps the tree "complete", but may break the
// invariant, since the new leaf could be smaller than its parent.
}using System.Collections.Generic;
// A binary heap is stored in a flat list. For the node at index i:
// left child = 2i+1, right child = 2i+2, parent = (i-1)/2.
// The heap invariant: every parent is <= its children, so the min is at index 0.
public class MinHeap {
private readonly List<int> data = new List<int>();
public void Push(int x) {
// Append at the end — that keeps the tree "complete", but may break the
// invariant, since the new leaf could be smaller than its parent.
data.Add(x);
}
}using System.Collections.Generic;
// A binary heap is stored in a flat list. For the node at index i:
// left child = 2i+1, right child = 2i+2, parent = (i-1)/2.
// The heap invariant: every parent is <= its children, so the min is at index 0.
public class MinHeap {
private readonly List<int> data = new List<int>();
public void Push(int x) {
// Append at the end — that keeps the tree "complete", but may break the
// invariant, since the new leaf could be smaller than its parent.
data.Add(x);
// Bubble the newcomer up until it's >= its parent again.
}
}using System.Collections.Generic;
// A binary heap is stored in a flat list. For the node at index i:
// left child = 2i+1, right child = 2i+2, parent = (i-1)/2.
// The heap invariant: every parent is <= its children, so the min is at index 0.
public class MinHeap {
private readonly List<int> data = new List<int>();
public void Push(int x) {
// Append at the end — that keeps the tree "complete", but may break the
// invariant, since the new leaf could be smaller than its parent.
data.Add(x);
// Bubble the newcomer up until it's >= its parent again.
Up(data.Count - 1);
}
}using System.Collections.Generic;
// A binary heap is stored in a flat list. For the node at index i:
// left child = 2i+1, right child = 2i+2, parent = (i-1)/2.
// The heap invariant: every parent is <= its children, so the min is at index 0.
public class MinHeap {
private readonly List<int> data = new List<int>();
public void Push(int x) {
// Append at the end — that keeps the tree "complete", but may break the
// invariant, since the new leaf could be smaller than its parent.
data.Add(x);
// Bubble the newcomer up until it's >= its parent again.
Up(data.Count - 1);
}
// The min lives at the root. Swap it with the last leaf so we can remove it
// from the end cheaply.
}using System.Collections.Generic;
// A binary heap is stored in a flat list. For the node at index i:
// left child = 2i+1, right child = 2i+2, parent = (i-1)/2.
// The heap invariant: every parent is <= its children, so the min is at index 0.
public class MinHeap {
private readonly List<int> data = new List<int>();
public void Push(int x) {
// Append at the end — that keeps the tree "complete", but may break the
// invariant, since the new leaf could be smaller than its parent.
data.Add(x);
// Bubble the newcomer up until it's >= its parent again.
Up(data.Count - 1);
}
public int Pop() {
// The min lives at the root. Swap it with the last leaf so we can remove it
// from the end cheaply.
int n = data.Count - 1;
(data[0], data[n]) = (data[n], data[0]);
int min = data[n];
}
}using System.Collections.Generic;
// A binary heap is stored in a flat list. For the node at index i:
// left child = 2i+1, right child = 2i+2, parent = (i-1)/2.
// The heap invariant: every parent is <= its children, so the min is at index 0.
public class MinHeap {
private readonly List<int> data = new List<int>();
public void Push(int x) {
// Append at the end — that keeps the tree "complete", but may break the
// invariant, since the new leaf could be smaller than its parent.
data.Add(x);
// Bubble the newcomer up until it's >= its parent again.
Up(data.Count - 1);
}
public int Pop() {
// The min lives at the root. Swap it with the last leaf so we can remove it
// from the end cheaply.
int n = data.Count - 1;
(data[0], data[n]) = (data[n], data[0]);
int min = data[n];
// Drop the old min, then sift the leaf that's now at the root back down.
}
}using System.Collections.Generic;
// A binary heap is stored in a flat list. For the node at index i:
// left child = 2i+1, right child = 2i+2, parent = (i-1)/2.
// The heap invariant: every parent is <= its children, so the min is at index 0.
public class MinHeap {
private readonly List<int> data = new List<int>();
public void Push(int x) {
// Append at the end — that keeps the tree "complete", but may break the
// invariant, since the new leaf could be smaller than its parent.
data.Add(x);
// Bubble the newcomer up until it's >= its parent again.
Up(data.Count - 1);
}
public int Pop() {
// The min lives at the root. Swap it with the last leaf so we can remove it
// from the end cheaply.
int n = data.Count - 1;
(data[0], data[n]) = (data[n], data[0]);
int min = data[n];
// Drop the old min, then sift the leaf that's now at the root back down.
data.RemoveAt(n);
Down(0);
return min;
}
}using System.Collections.Generic;
// A binary heap is stored in a flat list. For the node at index i:
// left child = 2i+1, right child = 2i+2, parent = (i-1)/2.
// The heap invariant: every parent is <= its children, so the min is at index 0.
public class MinHeap {
private readonly List<int> data = new List<int>();
public void Push(int x) {
// Append at the end — that keeps the tree "complete", but may break the
// invariant, since the new leaf could be smaller than its parent.
data.Add(x);
// Bubble the newcomer up until it's >= its parent again.
Up(data.Count - 1);
}
public int Pop() {
// The min lives at the root. Swap it with the last leaf so we can remove it
// from the end cheaply.
int n = data.Count - 1;
(data[0], data[n]) = (data[n], data[0]);
int min = data[n];
// Drop the old min, then sift the leaf that's now at the root back down.
data.RemoveAt(n);
Down(0);
return min;
}
// Up: while a node is smaller than its parent, swap them and follow it upward.
}using System.Collections.Generic;
// A binary heap is stored in a flat list. For the node at index i:
// left child = 2i+1, right child = 2i+2, parent = (i-1)/2.
// The heap invariant: every parent is <= its children, so the min is at index 0.
public class MinHeap {
private readonly List<int> data = new List<int>();
public void Push(int x) {
// Append at the end — that keeps the tree "complete", but may break the
// invariant, since the new leaf could be smaller than its parent.
data.Add(x);
// Bubble the newcomer up until it's >= its parent again.
Up(data.Count - 1);
}
public int Pop() {
// The min lives at the root. Swap it with the last leaf so we can remove it
// from the end cheaply.
int n = data.Count - 1;
(data[0], data[n]) = (data[n], data[0]);
int min = data[n];
// Drop the old min, then sift the leaf that's now at the root back down.
data.RemoveAt(n);
Down(0);
return min;
}
// Up: while a node is smaller than its parent, swap them and follow it upward.
private void Up(int i) {
while (i > 0) {
int parent = (i - 1) / 2;
if (data[parent] <= data[i]) {
break; // parent already <= node: invariant restored
}
(data[parent], data[i]) = (data[i], data[parent]);
i = parent;
}
}
}using System.Collections.Generic;
// A binary heap is stored in a flat list. For the node at index i:
// left child = 2i+1, right child = 2i+2, parent = (i-1)/2.
// The heap invariant: every parent is <= its children, so the min is at index 0.
public class MinHeap {
private readonly List<int> data = new List<int>();
public void Push(int x) {
// Append at the end — that keeps the tree "complete", but may break the
// invariant, since the new leaf could be smaller than its parent.
data.Add(x);
// Bubble the newcomer up until it's >= its parent again.
Up(data.Count - 1);
}
public int Pop() {
// The min lives at the root. Swap it with the last leaf so we can remove it
// from the end cheaply.
int n = data.Count - 1;
(data[0], data[n]) = (data[n], data[0]);
int min = data[n];
// Drop the old min, then sift the leaf that's now at the root back down.
data.RemoveAt(n);
Down(0);
return min;
}
// Up: while a node is smaller than its parent, swap them and follow it upward.
private void Up(int i) {
while (i > 0) {
int parent = (i - 1) / 2;
if (data[parent] <= data[i]) {
break; // parent already <= node: invariant restored
}
(data[parent], data[i]) = (data[i], data[parent]);
i = parent;
}
}
// Down: repeatedly swap a node with its SMALLEST child until it sits above both.
// Assume i is smallest, then check its two children.
}using System.Collections.Generic;
// A binary heap is stored in a flat list. For the node at index i:
// left child = 2i+1, right child = 2i+2, parent = (i-1)/2.
// The heap invariant: every parent is <= its children, so the min is at index 0.
public class MinHeap {
private readonly List<int> data = new List<int>();
public void Push(int x) {
// Append at the end — that keeps the tree "complete", but may break the
// invariant, since the new leaf could be smaller than its parent.
data.Add(x);
// Bubble the newcomer up until it's >= its parent again.
Up(data.Count - 1);
}
public int Pop() {
// The min lives at the root. Swap it with the last leaf so we can remove it
// from the end cheaply.
int n = data.Count - 1;
(data[0], data[n]) = (data[n], data[0]);
int min = data[n];
// Drop the old min, then sift the leaf that's now at the root back down.
data.RemoveAt(n);
Down(0);
return min;
}
// Up: while a node is smaller than its parent, swap them and follow it upward.
private void Up(int i) {
while (i > 0) {
int parent = (i - 1) / 2;
if (data[parent] <= data[i]) {
break; // parent already <= node: invariant restored
}
(data[parent], data[i]) = (data[i], data[parent]);
i = parent;
}
}
// Down: repeatedly swap a node with its SMALLEST child until it sits above both.
private void Down(int i) {
int n = data.Count;
while (true) {
// Assume i is smallest, then check its two children.
int smallest = i, l = 2 * i + 1, r = 2 * i + 2;
if (l < n && data[l] < data[smallest]) {
smallest = l;
}
if (r < n && data[r] < data[smallest]) {
smallest = r;
}
if (smallest == i) {
break; // node is already <= both children
}
(data[i], data[smallest]) = (data[smallest], data[i]);
i = smallest;
}
}
}// A binary heap is stored in a flat array. For the node at index i:
// left child = 2i+1, right child = 2i+2, parent = (i-1)/2.
// The heap invariant: every parent is <= its children, so the min is at index 0.
// The capacity is fixed so the example stays about the heap logic; a real one
// would grow the array with realloc.
#define HEAP_CAP 1024
typedef struct {
int data[HEAP_CAP];
int size;
} MinHeap;
// Declared up front so heapPush and heapPop can call them before they are
// defined below.
void heapUp(MinHeap* h, int i);
void heapDown(MinHeap* h, int i);
// C has no multiple assignment, so a helper keeps the swaps readable.
static void swapInt(int* a, int* b) {
int t = *a;
*a = *b;
*b = t;
}// A binary heap is stored in a flat array. For the node at index i:
// left child = 2i+1, right child = 2i+2, parent = (i-1)/2.
// The heap invariant: every parent is <= its children, so the min is at index 0.
// The capacity is fixed so the example stays about the heap logic; a real one
// would grow the array with realloc.
#define HEAP_CAP 1024
typedef struct {
int data[HEAP_CAP];
int size;
} MinHeap;
// Declared up front so heapPush and heapPop can call them before they are
// defined below.
void heapUp(MinHeap* h, int i);
void heapDown(MinHeap* h, int i);
// C has no multiple assignment, so a helper keeps the swaps readable.
static void swapInt(int* a, int* b) {
int t = *a;
*a = *b;
*b = t;
}
// Append at the end — that keeps the tree "complete", but may break the
// invariant, since the new leaf could be smaller than its parent.
// A binary heap is stored in a flat array. For the node at index i:
// left child = 2i+1, right child = 2i+2, parent = (i-1)/2.
// The heap invariant: every parent is <= its children, so the min is at index 0.
// The capacity is fixed so the example stays about the heap logic; a real one
// would grow the array with realloc.
#define HEAP_CAP 1024
typedef struct {
int data[HEAP_CAP];
int size;
} MinHeap;
// Declared up front so heapPush and heapPop can call them before they are
// defined below.
void heapUp(MinHeap* h, int i);
void heapDown(MinHeap* h, int i);
// C has no multiple assignment, so a helper keeps the swaps readable.
static void swapInt(int* a, int* b) {
int t = *a;
*a = *b;
*b = t;
}
void heapPush(MinHeap* h, int x) {
// Append at the end — that keeps the tree "complete", but may break the
// invariant, since the new leaf could be smaller than its parent.
h->data[h->size++] = x;
}// A binary heap is stored in a flat array. For the node at index i:
// left child = 2i+1, right child = 2i+2, parent = (i-1)/2.
// The heap invariant: every parent is <= its children, so the min is at index 0.
// The capacity is fixed so the example stays about the heap logic; a real one
// would grow the array with realloc.
#define HEAP_CAP 1024
typedef struct {
int data[HEAP_CAP];
int size;
} MinHeap;
// Declared up front so heapPush and heapPop can call them before they are
// defined below.
void heapUp(MinHeap* h, int i);
void heapDown(MinHeap* h, int i);
// C has no multiple assignment, so a helper keeps the swaps readable.
static void swapInt(int* a, int* b) {
int t = *a;
*a = *b;
*b = t;
}
void heapPush(MinHeap* h, int x) {
// Append at the end — that keeps the tree "complete", but may break the
// invariant, since the new leaf could be smaller than its parent.
h->data[h->size++] = x;
// Bubble the newcomer up until it's >= its parent again.
}// A binary heap is stored in a flat array. For the node at index i:
// left child = 2i+1, right child = 2i+2, parent = (i-1)/2.
// The heap invariant: every parent is <= its children, so the min is at index 0.
// The capacity is fixed so the example stays about the heap logic; a real one
// would grow the array with realloc.
#define HEAP_CAP 1024
typedef struct {
int data[HEAP_CAP];
int size;
} MinHeap;
// Declared up front so heapPush and heapPop can call them before they are
// defined below.
void heapUp(MinHeap* h, int i);
void heapDown(MinHeap* h, int i);
// C has no multiple assignment, so a helper keeps the swaps readable.
static void swapInt(int* a, int* b) {
int t = *a;
*a = *b;
*b = t;
}
void heapPush(MinHeap* h, int x) {
// Append at the end — that keeps the tree "complete", but may break the
// invariant, since the new leaf could be smaller than its parent.
h->data[h->size++] = x;
// Bubble the newcomer up until it's >= its parent again.
heapUp(h, h->size - 1);
}// A binary heap is stored in a flat array. For the node at index i:
// left child = 2i+1, right child = 2i+2, parent = (i-1)/2.
// The heap invariant: every parent is <= its children, so the min is at index 0.
// The capacity is fixed so the example stays about the heap logic; a real one
// would grow the array with realloc.
#define HEAP_CAP 1024
typedef struct {
int data[HEAP_CAP];
int size;
} MinHeap;
// Declared up front so heapPush and heapPop can call them before they are
// defined below.
void heapUp(MinHeap* h, int i);
void heapDown(MinHeap* h, int i);
// C has no multiple assignment, so a helper keeps the swaps readable.
static void swapInt(int* a, int* b) {
int t = *a;
*a = *b;
*b = t;
}
void heapPush(MinHeap* h, int x) {
// Append at the end — that keeps the tree "complete", but may break the
// invariant, since the new leaf could be smaller than its parent.
h->data[h->size++] = x;
// Bubble the newcomer up until it's >= its parent again.
heapUp(h, h->size - 1);
}
// The min lives at the root. Swap it with the last leaf so we can remove it
// from the end cheaply.
// A binary heap is stored in a flat array. For the node at index i:
// left child = 2i+1, right child = 2i+2, parent = (i-1)/2.
// The heap invariant: every parent is <= its children, so the min is at index 0.
// The capacity is fixed so the example stays about the heap logic; a real one
// would grow the array with realloc.
#define HEAP_CAP 1024
typedef struct {
int data[HEAP_CAP];
int size;
} MinHeap;
// Declared up front so heapPush and heapPop can call them before they are
// defined below.
void heapUp(MinHeap* h, int i);
void heapDown(MinHeap* h, int i);
// C has no multiple assignment, so a helper keeps the swaps readable.
static void swapInt(int* a, int* b) {
int t = *a;
*a = *b;
*b = t;
}
void heapPush(MinHeap* h, int x) {
// Append at the end — that keeps the tree "complete", but may break the
// invariant, since the new leaf could be smaller than its parent.
h->data[h->size++] = x;
// Bubble the newcomer up until it's >= its parent again.
heapUp(h, h->size - 1);
}
int heapPop(MinHeap* h) {
// The min lives at the root. Swap it with the last leaf so we can remove it
// from the end cheaply.
int n = h->size - 1;
swapInt(&h->data[0], &h->data[n]);
int min = h->data[n];
}// A binary heap is stored in a flat array. For the node at index i:
// left child = 2i+1, right child = 2i+2, parent = (i-1)/2.
// The heap invariant: every parent is <= its children, so the min is at index 0.
// The capacity is fixed so the example stays about the heap logic; a real one
// would grow the array with realloc.
#define HEAP_CAP 1024
typedef struct {
int data[HEAP_CAP];
int size;
} MinHeap;
// Declared up front so heapPush and heapPop can call them before they are
// defined below.
void heapUp(MinHeap* h, int i);
void heapDown(MinHeap* h, int i);
// C has no multiple assignment, so a helper keeps the swaps readable.
static void swapInt(int* a, int* b) {
int t = *a;
*a = *b;
*b = t;
}
void heapPush(MinHeap* h, int x) {
// Append at the end — that keeps the tree "complete", but may break the
// invariant, since the new leaf could be smaller than its parent.
h->data[h->size++] = x;
// Bubble the newcomer up until it's >= its parent again.
heapUp(h, h->size - 1);
}
int heapPop(MinHeap* h) {
// The min lives at the root. Swap it with the last leaf so we can remove it
// from the end cheaply.
int n = h->size - 1;
swapInt(&h->data[0], &h->data[n]);
int min = h->data[n];
// Drop the old min, then sift the leaf that's now at the root back down.
}// A binary heap is stored in a flat array. For the node at index i:
// left child = 2i+1, right child = 2i+2, parent = (i-1)/2.
// The heap invariant: every parent is <= its children, so the min is at index 0.
// The capacity is fixed so the example stays about the heap logic; a real one
// would grow the array with realloc.
#define HEAP_CAP 1024
typedef struct {
int data[HEAP_CAP];
int size;
} MinHeap;
// Declared up front so heapPush and heapPop can call them before they are
// defined below.
void heapUp(MinHeap* h, int i);
void heapDown(MinHeap* h, int i);
// C has no multiple assignment, so a helper keeps the swaps readable.
static void swapInt(int* a, int* b) {
int t = *a;
*a = *b;
*b = t;
}
void heapPush(MinHeap* h, int x) {
// Append at the end — that keeps the tree "complete", but may break the
// invariant, since the new leaf could be smaller than its parent.
h->data[h->size++] = x;
// Bubble the newcomer up until it's >= its parent again.
heapUp(h, h->size - 1);
}
int heapPop(MinHeap* h) {
// The min lives at the root. Swap it with the last leaf so we can remove it
// from the end cheaply.
int n = h->size - 1;
swapInt(&h->data[0], &h->data[n]);
int min = h->data[n];
// Drop the old min, then sift the leaf that's now at the root back down.
h->size = n;
heapDown(h, 0);
return min;
}// A binary heap is stored in a flat array. For the node at index i:
// left child = 2i+1, right child = 2i+2, parent = (i-1)/2.
// The heap invariant: every parent is <= its children, so the min is at index 0.
// The capacity is fixed so the example stays about the heap logic; a real one
// would grow the array with realloc.
#define HEAP_CAP 1024
typedef struct {
int data[HEAP_CAP];
int size;
} MinHeap;
// Declared up front so heapPush and heapPop can call them before they are
// defined below.
void heapUp(MinHeap* h, int i);
void heapDown(MinHeap* h, int i);
// C has no multiple assignment, so a helper keeps the swaps readable.
static void swapInt(int* a, int* b) {
int t = *a;
*a = *b;
*b = t;
}
void heapPush(MinHeap* h, int x) {
// Append at the end — that keeps the tree "complete", but may break the
// invariant, since the new leaf could be smaller than its parent.
h->data[h->size++] = x;
// Bubble the newcomer up until it's >= its parent again.
heapUp(h, h->size - 1);
}
int heapPop(MinHeap* h) {
// The min lives at the root. Swap it with the last leaf so we can remove it
// from the end cheaply.
int n = h->size - 1;
swapInt(&h->data[0], &h->data[n]);
int min = h->data[n];
// Drop the old min, then sift the leaf that's now at the root back down.
h->size = n;
heapDown(h, 0);
return min;
}
// heapUp: while a node is smaller than its parent, swap them and follow it upward.
// A binary heap is stored in a flat array. For the node at index i:
// left child = 2i+1, right child = 2i+2, parent = (i-1)/2.
// The heap invariant: every parent is <= its children, so the min is at index 0.
// The capacity is fixed so the example stays about the heap logic; a real one
// would grow the array with realloc.
#define HEAP_CAP 1024
typedef struct {
int data[HEAP_CAP];
int size;
} MinHeap;
// Declared up front so heapPush and heapPop can call them before they are
// defined below.
void heapUp(MinHeap* h, int i);
void heapDown(MinHeap* h, int i);
// C has no multiple assignment, so a helper keeps the swaps readable.
static void swapInt(int* a, int* b) {
int t = *a;
*a = *b;
*b = t;
}
void heapPush(MinHeap* h, int x) {
// Append at the end — that keeps the tree "complete", but may break the
// invariant, since the new leaf could be smaller than its parent.
h->data[h->size++] = x;
// Bubble the newcomer up until it's >= its parent again.
heapUp(h, h->size - 1);
}
int heapPop(MinHeap* h) {
// The min lives at the root. Swap it with the last leaf so we can remove it
// from the end cheaply.
int n = h->size - 1;
swapInt(&h->data[0], &h->data[n]);
int min = h->data[n];
// Drop the old min, then sift the leaf that's now at the root back down.
h->size = n;
heapDown(h, 0);
return min;
}
// heapUp: while a node is smaller than its parent, swap them and follow it upward.
void heapUp(MinHeap* h, int i) {
while (i > 0) {
int parent = (i - 1) / 2;
if (h->data[parent] <= h->data[i]) {
break; // parent already <= node: invariant restored
}
swapInt(&h->data[parent], &h->data[i]);
i = parent;
}
}// A binary heap is stored in a flat array. For the node at index i:
// left child = 2i+1, right child = 2i+2, parent = (i-1)/2.
// The heap invariant: every parent is <= its children, so the min is at index 0.
// The capacity is fixed so the example stays about the heap logic; a real one
// would grow the array with realloc.
#define HEAP_CAP 1024
typedef struct {
int data[HEAP_CAP];
int size;
} MinHeap;
// Declared up front so heapPush and heapPop can call them before they are
// defined below.
void heapUp(MinHeap* h, int i);
void heapDown(MinHeap* h, int i);
// C has no multiple assignment, so a helper keeps the swaps readable.
static void swapInt(int* a, int* b) {
int t = *a;
*a = *b;
*b = t;
}
void heapPush(MinHeap* h, int x) {
// Append at the end — that keeps the tree "complete", but may break the
// invariant, since the new leaf could be smaller than its parent.
h->data[h->size++] = x;
// Bubble the newcomer up until it's >= its parent again.
heapUp(h, h->size - 1);
}
int heapPop(MinHeap* h) {
// The min lives at the root. Swap it with the last leaf so we can remove it
// from the end cheaply.
int n = h->size - 1;
swapInt(&h->data[0], &h->data[n]);
int min = h->data[n];
// Drop the old min, then sift the leaf that's now at the root back down.
h->size = n;
heapDown(h, 0);
return min;
}
// heapUp: while a node is smaller than its parent, swap them and follow it upward.
void heapUp(MinHeap* h, int i) {
while (i > 0) {
int parent = (i - 1) / 2;
if (h->data[parent] <= h->data[i]) {
break; // parent already <= node: invariant restored
}
swapInt(&h->data[parent], &h->data[i]);
i = parent;
}
}
// heapDown: repeatedly swap a node with its SMALLEST child until it sits above both.
// Assume i is smallest, then check its two children.
// A binary heap is stored in a flat array. For the node at index i:
// left child = 2i+1, right child = 2i+2, parent = (i-1)/2.
// The heap invariant: every parent is <= its children, so the min is at index 0.
// The capacity is fixed so the example stays about the heap logic; a real one
// would grow the array with realloc.
#define HEAP_CAP 1024
typedef struct {
int data[HEAP_CAP];
int size;
} MinHeap;
// Declared up front so heapPush and heapPop can call them before they are
// defined below.
void heapUp(MinHeap* h, int i);
void heapDown(MinHeap* h, int i);
// C has no multiple assignment, so a helper keeps the swaps readable.
static void swapInt(int* a, int* b) {
int t = *a;
*a = *b;
*b = t;
}
void heapPush(MinHeap* h, int x) {
// Append at the end — that keeps the tree "complete", but may break the
// invariant, since the new leaf could be smaller than its parent.
h->data[h->size++] = x;
// Bubble the newcomer up until it's >= its parent again.
heapUp(h, h->size - 1);
}
int heapPop(MinHeap* h) {
// The min lives at the root. Swap it with the last leaf so we can remove it
// from the end cheaply.
int n = h->size - 1;
swapInt(&h->data[0], &h->data[n]);
int min = h->data[n];
// Drop the old min, then sift the leaf that's now at the root back down.
h->size = n;
heapDown(h, 0);
return min;
}
// heapUp: while a node is smaller than its parent, swap them and follow it upward.
void heapUp(MinHeap* h, int i) {
while (i > 0) {
int parent = (i - 1) / 2;
if (h->data[parent] <= h->data[i]) {
break; // parent already <= node: invariant restored
}
swapInt(&h->data[parent], &h->data[i]);
i = parent;
}
}
// heapDown: repeatedly swap a node with its SMALLEST child until it sits above both.
void heapDown(MinHeap* h, int i) {
int n = h->size;
while (1) {
// Assume i is smallest, then check its two children.
int smallest = i, l = 2 * i + 1, r = 2 * i + 2;
if (l < n && h->data[l] < h->data[smallest]) {
smallest = l;
}
if (r < n && h->data[r] < h->data[smallest]) {
smallest = r;
}
if (smallest == i) {
break; // node is already <= both children
}
swapInt(&h->data[i], &h->data[smallest]);
i = smallest;
}
}#include <vector>
using namespace std;
// A binary heap is stored in a flat vector. For the node at index i:
// left child = 2i+1, right child = 2i+2, parent = (i-1)/2.
// The heap invariant: every parent is <= its children, so the min is at index 0.
class MinHeap {
vector<int> data;
};#include <vector>
using namespace std;
// A binary heap is stored in a flat vector. For the node at index i:
// left child = 2i+1, right child = 2i+2, parent = (i-1)/2.
// The heap invariant: every parent is <= its children, so the min is at index 0.
class MinHeap {
vector<int> data;
// Append at the end — that keeps the tree "complete", but may break the
// invariant, since the new leaf could be smaller than its parent.
};#include <vector>
using namespace std;
// A binary heap is stored in a flat vector. For the node at index i:
// left child = 2i+1, right child = 2i+2, parent = (i-1)/2.
// The heap invariant: every parent is <= its children, so the min is at index 0.
class MinHeap {
vector<int> data;
public:
void push(int x) {
// Append at the end — that keeps the tree "complete", but may break the
// invariant, since the new leaf could be smaller than its parent.
data.push_back(x);
}
};#include <vector>
using namespace std;
// A binary heap is stored in a flat vector. For the node at index i:
// left child = 2i+1, right child = 2i+2, parent = (i-1)/2.
// The heap invariant: every parent is <= its children, so the min is at index 0.
class MinHeap {
vector<int> data;
public:
void push(int x) {
// Append at the end — that keeps the tree "complete", but may break the
// invariant, since the new leaf could be smaller than its parent.
data.push_back(x);
// Bubble the newcomer up until it's >= its parent again.
}
};#include <vector>
using namespace std;
// A binary heap is stored in a flat vector. For the node at index i:
// left child = 2i+1, right child = 2i+2, parent = (i-1)/2.
// The heap invariant: every parent is <= its children, so the min is at index 0.
class MinHeap {
vector<int> data;
public:
void push(int x) {
// Append at the end — that keeps the tree "complete", but may break the
// invariant, since the new leaf could be smaller than its parent.
data.push_back(x);
// Bubble the newcomer up until it's >= its parent again.
up((int)data.size() - 1);
}
};#include <vector>
using namespace std;
// A binary heap is stored in a flat vector. For the node at index i:
// left child = 2i+1, right child = 2i+2, parent = (i-1)/2.
// The heap invariant: every parent is <= its children, so the min is at index 0.
class MinHeap {
vector<int> data;
public:
void push(int x) {
// Append at the end — that keeps the tree "complete", but may break the
// invariant, since the new leaf could be smaller than its parent.
data.push_back(x);
// Bubble the newcomer up until it's >= its parent again.
up((int)data.size() - 1);
}
// The min lives at the root. Swap it with the last leaf so we can remove it
// from the end cheaply.
};#include <vector>
using namespace std;
// A binary heap is stored in a flat vector. For the node at index i:
// left child = 2i+1, right child = 2i+2, parent = (i-1)/2.
// The heap invariant: every parent is <= its children, so the min is at index 0.
class MinHeap {
vector<int> data;
public:
void push(int x) {
// Append at the end — that keeps the tree "complete", but may break the
// invariant, since the new leaf could be smaller than its parent.
data.push_back(x);
// Bubble the newcomer up until it's >= its parent again.
up((int)data.size() - 1);
}
int pop() {
// The min lives at the root. Swap it with the last leaf so we can remove it
// from the end cheaply.
int n = (int)data.size() - 1;
swap(data[0], data[n]);
int min = data[n];
}
};#include <vector>
using namespace std;
// A binary heap is stored in a flat vector. For the node at index i:
// left child = 2i+1, right child = 2i+2, parent = (i-1)/2.
// The heap invariant: every parent is <= its children, so the min is at index 0.
class MinHeap {
vector<int> data;
public:
void push(int x) {
// Append at the end — that keeps the tree "complete", but may break the
// invariant, since the new leaf could be smaller than its parent.
data.push_back(x);
// Bubble the newcomer up until it's >= its parent again.
up((int)data.size() - 1);
}
int pop() {
// The min lives at the root. Swap it with the last leaf so we can remove it
// from the end cheaply.
int n = (int)data.size() - 1;
swap(data[0], data[n]);
int min = data[n];
// Drop the old min, then sift the leaf that's now at the root back down.
}
};#include <vector>
using namespace std;
// A binary heap is stored in a flat vector. For the node at index i:
// left child = 2i+1, right child = 2i+2, parent = (i-1)/2.
// The heap invariant: every parent is <= its children, so the min is at index 0.
class MinHeap {
vector<int> data;
public:
void push(int x) {
// Append at the end — that keeps the tree "complete", but may break the
// invariant, since the new leaf could be smaller than its parent.
data.push_back(x);
// Bubble the newcomer up until it's >= its parent again.
up((int)data.size() - 1);
}
int pop() {
// The min lives at the root. Swap it with the last leaf so we can remove it
// from the end cheaply.
int n = (int)data.size() - 1;
swap(data[0], data[n]);
int min = data[n];
// Drop the old min, then sift the leaf that's now at the root back down.
data.pop_back();
down(0);
return min;
}
};#include <vector>
using namespace std;
// A binary heap is stored in a flat vector. For the node at index i:
// left child = 2i+1, right child = 2i+2, parent = (i-1)/2.
// The heap invariant: every parent is <= its children, so the min is at index 0.
class MinHeap {
vector<int> data;
public:
void push(int x) {
// Append at the end — that keeps the tree "complete", but may break the
// invariant, since the new leaf could be smaller than its parent.
data.push_back(x);
// Bubble the newcomer up until it's >= its parent again.
up((int)data.size() - 1);
}
int pop() {
// The min lives at the root. Swap it with the last leaf so we can remove it
// from the end cheaply.
int n = (int)data.size() - 1;
swap(data[0], data[n]);
int min = data[n];
// Drop the old min, then sift the leaf that's now at the root back down.
data.pop_back();
down(0);
return min;
}
private:
// up: while a node is smaller than its parent, swap them and follow it upward.
};#include <vector>
using namespace std;
// A binary heap is stored in a flat vector. For the node at index i:
// left child = 2i+1, right child = 2i+2, parent = (i-1)/2.
// The heap invariant: every parent is <= its children, so the min is at index 0.
class MinHeap {
vector<int> data;
public:
void push(int x) {
// Append at the end — that keeps the tree "complete", but may break the
// invariant, since the new leaf could be smaller than its parent.
data.push_back(x);
// Bubble the newcomer up until it's >= its parent again.
up((int)data.size() - 1);
}
int pop() {
// The min lives at the root. Swap it with the last leaf so we can remove it
// from the end cheaply.
int n = (int)data.size() - 1;
swap(data[0], data[n]);
int min = data[n];
// Drop the old min, then sift the leaf that's now at the root back down.
data.pop_back();
down(0);
return min;
}
private:
// up: while a node is smaller than its parent, swap them and follow it upward.
void up(int i) {
while (i > 0) {
int parent = (i - 1) / 2;
if (data[parent] <= data[i]) {
break; // parent already <= node: invariant restored
}
swap(data[parent], data[i]);
i = parent;
}
}
};#include <vector>
using namespace std;
// A binary heap is stored in a flat vector. For the node at index i:
// left child = 2i+1, right child = 2i+2, parent = (i-1)/2.
// The heap invariant: every parent is <= its children, so the min is at index 0.
class MinHeap {
vector<int> data;
public:
void push(int x) {
// Append at the end — that keeps the tree "complete", but may break the
// invariant, since the new leaf could be smaller than its parent.
data.push_back(x);
// Bubble the newcomer up until it's >= its parent again.
up((int)data.size() - 1);
}
int pop() {
// The min lives at the root. Swap it with the last leaf so we can remove it
// from the end cheaply.
int n = (int)data.size() - 1;
swap(data[0], data[n]);
int min = data[n];
// Drop the old min, then sift the leaf that's now at the root back down.
data.pop_back();
down(0);
return min;
}
private:
// up: while a node is smaller than its parent, swap them and follow it upward.
void up(int i) {
while (i > 0) {
int parent = (i - 1) / 2;
if (data[parent] <= data[i]) {
break; // parent already <= node: invariant restored
}
swap(data[parent], data[i]);
i = parent;
}
}
// down: repeatedly swap a node with its SMALLEST child until it sits above both.
// Assume i is smallest, then check its two children.
};#include <vector>
using namespace std;
// A binary heap is stored in a flat vector. For the node at index i:
// left child = 2i+1, right child = 2i+2, parent = (i-1)/2.
// The heap invariant: every parent is <= its children, so the min is at index 0.
class MinHeap {
vector<int> data;
public:
void push(int x) {
// Append at the end — that keeps the tree "complete", but may break the
// invariant, since the new leaf could be smaller than its parent.
data.push_back(x);
// Bubble the newcomer up until it's >= its parent again.
up((int)data.size() - 1);
}
int pop() {
// The min lives at the root. Swap it with the last leaf so we can remove it
// from the end cheaply.
int n = (int)data.size() - 1;
swap(data[0], data[n]);
int min = data[n];
// Drop the old min, then sift the leaf that's now at the root back down.
data.pop_back();
down(0);
return min;
}
private:
// up: while a node is smaller than its parent, swap them and follow it upward.
void up(int i) {
while (i > 0) {
int parent = (i - 1) / 2;
if (data[parent] <= data[i]) {
break; // parent already <= node: invariant restored
}
swap(data[parent], data[i]);
i = parent;
}
}
// down: repeatedly swap a node with its SMALLEST child until it sits above both.
void down(int i) {
int n = (int)data.size();
while (true) {
// Assume i is smallest, then check its two children.
int smallest = i, l = 2 * i + 1, r = 2 * i + 2;
if (l < n && data[l] < data[smallest]) {
smallest = l;
}
if (r < n && data[r] < data[smallest]) {
smallest = r;
}
if (smallest == i) {
break; // node is already <= both children
}
swap(data[i], data[smallest]);
i = smallest;
}
}
};Tap the left half to go back, the right half to go forward.
Arrow keys or space to navigate · Esc to exit.