image.png

1. 堆的概念

堆 - 图3

2. 简单实现

  1. package heap
  3. /**
  4. 使用数组来存储数据
  6. 从下标为 1 的位置开始存数据
  8. 节点：i
  9.     左节点：2 * i
  10.     右节点：2 * i + 1
  11.     父节点：i / 2
  12. */
  13. type Heap struct {
  14.     value []int
  15.     len   int
  16.     caps  int
  17. }
  19. /**
  20. 放入最后一个可插入的位置
  21. 然后从下往上调整
  22. */
  23. func (h *Heap) Push(v int) {
  24.     if h.len == h.caps {
  25.         panic("存不下了")
  26.     }
  28.     h.len++
  29.     h.value[h.len] = v
  31.     h.up()
  32. }
  34. func (h *Heap) Pop() int {
  35.     v := h.value[1]
  36.     h.value[1] = h.value[h.len] // 最后一位放到第一
  37.     h.len--
  39.     h.down()
  41.     return v
  42. }
  44. func (h *Heap) up() {
  45.     n, i := h.value[h.len], h.len
  46.     for n < h.value[i/2] && i > 0 {
  47.         h.value[i] = h.value[i/2]
  48.         h.value[i/2] = n
  49.         i = i / 2
  50.     }
  51. }
  53. func (h *Heap) down() {
  54.     n, i := h.value[1], 1
  56.     for {
  57.         i = i * 2
  59.         l, r := h.value[i], h.value[i+1]
  61.         if l < r {
  62.             i++
  63.         }
  65.         if i > h.len {
  66.             break
  67.         }
  69.         if h.value[i] > n {
  70.             h.value[i/2] = h.value[i]
  71.             h.value[i] = n
  72.         }
  73.     }
  74. }