From b52db3536079f08fca7505d8222a03ecc0a568d0 Mon Sep 17 00:00:00 2001
From: Runxi Yu
Date: Mon, 8 Jun 2026 05:47:08 +0000
Subject: internal/priorityqueue: Add

---
 internal/priorityqueue/doc.go        |  2 ++
 internal/priorityqueue/queue.go      | 45 ++++++++++++++++++++++++++++++++++++
 internal/priorityqueue/queue_test.go | 36 +++++++++++++++++++++++++++++
 internal/priorityqueue/sift.go       | 36 +++++++++++++++++++++++++++++
 4 files changed, 119 insertions(+)
 create mode 100644 internal/priorityqueue/doc.go
 create mode 100644 internal/priorityqueue/queue.go
 create mode 100644 internal/priorityqueue/queue_test.go
 create mode 100644 internal/priorityqueue/sift.go

diff --git a/internal/priorityqueue/doc.go b/internal/priorityqueue/doc.go
new file mode 100644
index 00000000..2cdd8522
--- /dev/null
+++ b/internal/priorityqueue/doc.go
@@ -0,0 +1,2 @@
+// Package priorityqueue provides a simple priority queue.
+package priorityqueue
diff --git a/internal/priorityqueue/queue.go b/internal/priorityqueue/queue.go
new file mode 100644
index 00000000..2d09add8
--- /dev/null
+++ b/internal/priorityqueue/queue.go
@@ -0,0 +1,45 @@
+package priorityqueue
+
+// Queue is one slice-backed priority queue.
+//
+// Labels: MT-Unsafe.
+type Queue[T any] struct {
+	items []T
+	less  func(left, right T) bool
+}
+
+// New builds one empty priority queue ordered by less.
+func New[T any](less func(left, right T) bool) *Queue[T] {
+	return &Queue[T]{less: less}
+}
+
+// Len reports the number of queued items.
+func (queue *Queue[T]) Len() int {
+	return len(queue.items)
+}
+
+// Pop removes one highest-priority item.
+func (queue *Queue[T]) Pop() (T, bool) {
+	if len(queue.items) == 0 {
+		var zero T
+
+		return zero, false
+	}
+
+	last := len(queue.items) - 1
+	top := queue.items[0]
+	queue.items[0] = queue.items[last]
+	queue.items = queue.items[:last]
+
+	if len(queue.items) > 0 {
+		queue.siftDown(0)
+	}
+
+	return top, true
+}
+
+// Push inserts one item.
+func (queue *Queue[T]) Push(item T) {
+	queue.items = append(queue.items, item)
+	queue.siftUp(len(queue.items) - 1)
+}
diff --git a/internal/priorityqueue/queue_test.go b/internal/priorityqueue/queue_test.go
new file mode 100644
index 00000000..14ed1ff6
--- /dev/null
+++ b/internal/priorityqueue/queue_test.go
@@ -0,0 +1,36 @@
+package priorityqueue_test
+
+import (
+	"slices"
+	"testing"
+
+	"lindenii.org/go/furgit/internal/priorityqueue"
+)
+
+func TestQueueAscending(t *testing.T) {
+	t.Parallel()
+
+	queue := priorityqueue.New(func(left, right int) bool {
+		return left < right
+	})
+
+	for _, value := range []int{5, 1, 4, 3, 2} {
+		queue.Push(value)
+	}
+
+	var got []int
+
+	for queue.Len() > 0 {
+		value, ok := queue.Pop()
+		if !ok {
+			t.Fatal("Pop should succeed")
+		}
+
+		got = append(got, value)
+	}
+
+	want := []int{1, 2, 3, 4, 5}
+	if !slices.Equal(got, want) {
+		t.Fatalf("pop order = %v, want %v", got, want)
+	}
+}
diff --git a/internal/priorityqueue/sift.go b/internal/priorityqueue/sift.go
new file mode 100644
index 00000000..e43e17a4
--- /dev/null
+++ b/internal/priorityqueue/sift.go
@@ -0,0 +1,36 @@
+package priorityqueue
+
+func (queue *Queue[T]) siftDown(idx int) {
+	for {
+		left := idx*2 + 1
+		if left >= len(queue.items) {
+			return
+		}
+
+		best := left
+
+		right := left + 1
+		if right < len(queue.items) && queue.less(queue.items[right], queue.items[left]) {
+			best = right
+		}
+
+		if !queue.less(queue.items[best], queue.items[idx]) {
+			return
+		}
+
+		queue.items[idx], queue.items[best] = queue.items[best], queue.items[idx]
+		idx = best
+	}
+}
+
+func (queue *Queue[T]) siftUp(idx int) {
+	for idx > 0 {
+		parent := (idx - 1) / 2
+		if !queue.less(queue.items[idx], queue.items[parent]) {
+			return
+		}
+
+		queue.items[idx], queue.items[parent] = queue.items[parent], queue.items[idx]
+		idx = parent
+	}
+}
-- 
cgit v1.3.1-10-gc9f91