ℹ️ New Book: Build Your Own Database
redis/13/heap.cpp
#include <stddef.h>
#include <stdint.h>
#include "heap.h"
static size_t heap_parent(size_t i) {
return (i + 1) / 2 - 1;
}
static size_t heap_left(size_t i) {
return i * 2 + 1;
}
static size_t heap_right(size_t i) {
return i * 2 + 2;
}
static void heap_up(HeapItem *a, size_t pos) {
HeapItem t = a[pos];
while (pos > 0 && a[heap_parent(pos)].val > t.val) {
// swap with the parent
a[pos] = a[heap_parent(pos)];
*a[pos].ref = pos;
pos = heap_parent(pos);
}
a[pos] = t;
*a[pos].ref = pos;
}
static void heap_down(HeapItem *a, size_t pos, size_t len) {
HeapItem t = a[pos];
while (true) {
// find the smallest one among the parent and their kids
size_t l = heap_left(pos);
size_t r = heap_right(pos);
size_t min_pos = -1;
size_t min_val = t.val;
if (l < len && a[l].val < min_val) {
min_pos = l;
min_val = a[l].val;
}
if (r < len && a[r].val < min_val) {
min_pos = r;
}
if (min_pos == (size_t)-1) {
break;
}
// swap with the kid
a[pos] = a[min_pos];
*a[pos].ref = pos;
pos = min_pos;
}
a[pos] = t;
*a[pos].ref = pos;
}
void heap_update(HeapItem *a, size_t pos, size_t len) {
if (pos > 0 && a[heap_parent(pos)].val > a[pos].val) {
heap_up(a, pos);
} else {
heap_down(a, pos, len);
}
}
See also:
codecrafters.io offers “Build Your Own X” courses in many programming languages.
Including Redis, Git, SQLite, Docker, and more.
Check it out
codecrafters.io offers “Build Your Own X” courses in many programming languages.
Including Redis, Git, SQLite, Docker, and more.