堆是解决优先级队列，topK问题的常见算法。
二叉堆的结构性质：堆是一个完全被填满的二叉树，一颗高位h的二叉树有 2^h到2^h+1 - 1个节点。
堆的性质：父节点的键值总是不大于它的孩子节点的键值（小顶堆）, 堆可以分为小顶堆和大顶堆。 以0开头的 数组中i处的左子节点为 2 * i + 1 右子节点在 2 * i + 2，子节点的父节点在 （i-1）/2处。具有有序性，但是不是说对插入的值是完全按照 单调的顺序排序的。
可以看出看出位于数组下标三的左子节点和右子节点符合定义，在 2 * 3 + 1 = 7【数组下标】； 2 * 3 + 2 = 8【数组下标8】
插入的操作
先插入到数组最后一个坐标下，如果可以放在最后一个坐标【符合二叉堆的性质】大于父节点【小顶堆】。如果不符合需要朝着父节点的方向一步一步上移。
如上图插入14的过程.
1:插入底部
2:上移 14 与父节点互换值
3:判断继续上移与父节点【21】互换值
到达条件退出上浮操作
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| function insert(&$arr, $value) {
$arr[] = $value;
$len = count($arr) - 1;
$i = $len;
while($i >= 0) {
$j = ($i - 1)/2;
if ($j >= 0 && $arr[$j] > $arr[$i]) {
$tmp = $arr[$i];
$arr[$i] = $arr[$j];
$arr[$j] = $tmp;
$i = $j;
} else {
break;
}
}
}
|
删除
删除其实和插入类似，把数组第一个节点数据取出作为返回数据，把数组最后一个元素取出用于比较，重新比较让结构符合二叉堆的性质。其实删除的是最后一个数组节点，其他数据通过比较运算一个放到合适的节点。
1:取出第一个数组的值 13 和最后一个值31
2:14 和 16比较 那个大小 决定往哪一个方向走，是往 14 左子树走，还是往16 的左子树走。用最后一个值【31】 与 当前走向的节点比较，如果最后一个值【31】如果大于当前节点继续往下进行。
代码实现：上图那些空的其实还保留着原来的值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| function del(&$arr) {
$midValue = $arr[0];
$len = count($arr) - 1;
$lastVal = $arr[$len];
$j = 0;
while (2 * $j <= $i) {
$left = 2 * $j + 1;
$right = 2 * $j + 2;
$t = $left;
if ($arr[$right && $arr[$right] < $arr[$left]) {
$t = $right;
}
if ($lastVal > $arr[$j]) {
$arr[$j] = $arr[$t];
$j = $t;
} else {
break;
}
}
$arr[$j] = $lastVal;
$unset[$arr[$len]];
return $arr;
}
|
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
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
|
<?php
class heap
{
public $heapArr = [];
protected $heapSize = -1;
public function init($testArr)
{
}
public function insert($val)
{
$this->heapSize++;
$this->heapArr[$this->heapSize] = $val;
$i = (count($this->heapArr) - 1);
while ($i >= 0) {
$j = ($i - 1) / 2;
if ($j >= 0 && $this->heapArr[$i] < $this->heapArr[$j]) {
$tmp = $this->heapArr[$i];
$this->heapArr[$i] = $this->heapArr[$j];
$this->heapArr[$j] = $tmp;
$i = $j;
} else {
break;
}
}
}
public function delete()
{
$i = (count($this->heapArr) - 1);
$minVal = $this->heapArr[0];
$lastVal = $this->heapArr[$i];
$j = 0;
while (2 * $j <= $i) {
$left = 2 * $j + 1;
$right = 2 * $j + 2;
$t = $left;
if ($this->heapArr[$left] && $this->heapArr[$right] && $this->heapArr[$right] < $this->heapArr[$left]) {
$t = $right;
}
if ($lastVal > $this->heapArr[$j]) {
$this->heapArr[$j] = $this->heapArr[$t];
$j = $t;
} else {
break;
}
}
$this->heapArr[$j] = $lastVal;
unset($this->heapArr[$i]);
$this->heapSize--;
return $minVal;
}
public function sort(array $arr)
{
$length = count($arr);
for ($i = ($length - 2) / 2; $i >= 0; $i--) {
$arr = $this->down($arr, $i, $length);
}
var_dump($arr);
for ($i = $length - 1; $i >= 1; $i--) {
$temp = $arr[$i];
$arr[$i] = $arr[0];
$arr[0] = $temp;
$arr = $this->down($arr, 0, $i);
}
return $arr;
}
public function down(array $arr, int $parent, int $length)
{
$temp = $arr[$parent];
$child = 2 * $parent + 1;
while ($child < $length) {
if ($child + 1 < $length && $arr[$child] > $arr[$child + 1]) {
$child++;
}
if ($temp <= $arr[$child]) {
break;
}
$arr[$parent] = $arr[$child];
$parent = $child;
$child = 2 * $parent + 1;
}
$arr[$parent] = $temp;
return $arr;
}
}
$testArr = [
31,
21,
19,
68,
26,
65,
19,
14,
13,
16,
32
];
$heap = new heap();
echo json_encode($heap->getTree($array,0));
|