algorithms/data-structures/heap/heap.go at main · microwind/algorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
/**
 * Copyright © https://github.com/microwind All rights reserved.
 * @author: jarryli@gmail.com
 * @version: 1.0
 * @description: 堆数据结构 - Go实现
 */

package main

import "fmt"

const MAX_SIZE = 100

/*
大顶堆：根节点始终为堆中的最大值。
         6
       /   \
      5     4
     / \   /
    3   2 1
*/
// 调整堆的结构，确保父节点大于或等于其子节点，符合大顶堆的性质
func heapifyMax(arr []int, n, i int) {
  largest := i     // 假设当前节点 i 为最大节点
  left := 2*i + 1  // 左子节点的索引
  right := 2*i + 2 // 右子节点的索引

  // 如果左子节点存在且大于当前最大值
  if left < n && arr[left] > arr[largest] {
    largest = left // 更新最大值索引
  }

  // 如果右子节点存在且大于当前最大值
  if right < n && arr[right] > arr[largest] {
    largest = right // 更新最大值索引
  }

  // 如果最大值不再是原节点 i，交换节点 i 和最大值节点
  if largest != i {
    arr[i], arr[largest] = arr[largest], arr[i]

    // 递归调整交换后的子树，确保其也符合大顶堆性质
    heapifyMax(arr, n, largest)
  }
}

/*
小顶堆：根节点始终为堆中的最小值。
         1
       /   \
      2     4
     / \   /
    5   3 6
*/
// 调整堆的结构，确保父节点小于或等于其子节点，符合小顶堆的性质
func heapifyMin(arr []int, n, i int) {
  smallest := i    // 假设当前节点 i 为最小节点
  left := 2*i + 1  // 左子节点的索引
  right := 2*i + 2 // 右子节点的索引

  // 如果左子节点存在且小于当前最小值
  if left < n && arr[left] < arr[smallest] {
    smallest = left // 更新最小值索引
  }

  // 如果右子节点存在且小于当前最小值
  if right < n && arr[right] < arr[smallest] {
    smallest = right // 更新最小值索引
  }

  // 如果最小值不再是原节点 i，交换节点 i 和最小值节点
  if smallest != i {
    arr[i], arr[smallest] = arr[smallest], arr[i]

    // 递归调整交换后的子树，确保其也符合小顶堆性质
    heapifyMin(arr, n, smallest)
  }
}

// 构建大顶堆
// 从最后一个非叶子节点开始，逐步调用 heapifyMax() 进行堆化
func buildMaxHeap(arr []int, n int) {
  // 从最后一个非叶子节点开始调整
  for i := n/2 - 1; i >= 0; i-- {
    heapifyMax(arr, n, i)
  }
}

// 构建小顶堆
// 从最后一个非叶子节点开始，逐步调用 heapifyMin() 进行堆化
func buildMinHeap(arr []int, n int) {
  // 从最后一个非叶子节点开始调整
  for i := n/2 - 1; i >= 0; i-- {
    heapifyMin(arr, n, i)
  }
}

// 打印堆
// 输出堆的内容
func printHeap(arr []int, n int) {
  for i := 0; i < n; i++ {
    fmt.Printf("%d ", arr[i])
  }
  fmt.Println()
}

func main() {
  // 初始化一个数组，用于构建大顶堆和小顶堆
  maxHeap := []int{3, 1, 6, 5, 2, 4}
  minHeap := []int{3, 1, 6, 5, 2, 4}

  // 计算数组的元素个数
  maxN := len(maxHeap)
  minN := len(minHeap)

  // 构建大顶堆
  buildMaxHeap(maxHeap, maxN)
  fmt.Print("Max heap: ")
  printHeap(maxHeap, maxN) // 输出大顶堆的结果

  // 构建小顶堆
  buildMinHeap(minHeap, minN)
  fmt.Print("Min heap: ")
  printHeap(minHeap, minN) // 输出小顶堆的结果
}

/*
jarry@MacBook-Pro heap % go run heap.go
Max heap: 6 5 4 1 2 3
Min heap: 1 2 4 5 3 6
*/