package astar6

// ============ 优先队列实现 ============
// 实现container/heap接口，用于高效获取f值最小的节点
// 相比sort.Slice，heap在动态插入/删除场景下性能更优
// Push/Pop复杂度: O(log n)
// 使用索引堆优化，updateHeap复杂度从O(n)优化为O(log n)

// heapItem 堆中的元素（索引堆实现）
type heapItem struct {
	node  *Node // 节点指针
	f     int32 // f = g + h
	index int   // 在堆中的索引位置，用于O(1)定位和O(log n)更新
}

// nodeHeap 最小堆，f值最小的节点在堆顶
type nodeHeap []*heapItem

// Len 返回堆的大小
func (h nodeHeap) Len() int { return len(h) }

// Less 比较函数，f值小的优先级高
func (h nodeHeap) Less(i, j int) bool { return h[i].f < h[j].f }

// Swap 交换两个元素，同时更新索引
func (h nodeHeap) Swap(i, j int) {
	h[i], h[j] = h[j], h[i]
	h[i].index = i
	h[j].index = j
}

// Push 向堆中添加元素
func (h *nodeHeap) Push(x interface{}) {
	item := x.(*heapItem)
	item.index = len(*h)
	*h = append(*h, item)
}

// Pop 从堆中取出最小元素
func (h *nodeHeap) Pop() interface{} {
	old := *h
	n := len(old)
	item := old[n-1]
	old[n-1] = nil // 置nil避免内存泄漏
	*h = old[0 : n-1]
	return item
}