php 中的堆数据结构是一种满足完全二叉树和堆性质(父结点值大于/小于子结点值)的树状结构,使用数组实现。堆支持两种操作:排序(从小到大提取最大元素)和优先级队列(根据优先级提取最大元素),分别通过 heapifyup 和 heapifydown 方法维护堆的性质。
PHP 中的堆数据结构:揭秘排序和优先级队列的奥秘
堆是一种树状数据结构,它满足以下两个性质:
- 完全二叉树性质:树中的每个结点都有两个子结点,或者没有子结点,形成一棵完全二叉树。
- 堆性质:每个父结点的值都大于(或等于)它的两个子结点的值(最大堆)或小于(或等于)它的两个子结点的值(最小堆)。
PHP 实现
在 PHP 中,我们使用数组来实现堆。以下是一个最大堆的 PHP 实现:
class MaxHeap {
private $heap = array();
private $size = 0;
public function insert($value) {
$this->heap[$this->size++] = $value;
$this->heapifyUp($this->size - 1);
}
private function heapifyUp($index) {
if ($index === 0) {
return;
}
$parentIndex = intval(($index - 1) / 2);
if ($this->heap[$index] > $this->heap[$parentIndex]) {
$temp = $this->heap[$index];
$this->heap[$index] = $this->heap[$parentIndex];
$this->heap[$parentIndex] = $temp;
$this->heapifyUp($parentIndex);
}
}
public function extractMax() {
if ($this->size === 0) {
return null;
}
$max = $this->heap[0];
$this->heap[0] = $this->heap[$this->size - 1];
$this->size--;
$this->heapifyDown(0);
return $max;
}
private function heapifyDown($index) {
$largestIndex = $index;
$leftIndex = 2 * $index + 1;
$rightIndex = 2 * $index + 2;
if ($leftIndex < $this->size && $this->heap[$leftIndex] > $this->heap[$largestIndex]) {
$largestIndex = $leftIndex;
}
if ($rightIndex < $this->size && $this->heap[$rightIndex] > $this->heap[$largestIndex]) {
$largestIndex = $rightIndex;
}
if ($largestIndex !== $index) {
$temp = $this->heap[$index];
$this->heap[$index] = $this->heap[$largestIndex];
$this->heap[$largestIndex] = $temp;
$this->heapifyDown($largestIndex);
}
}
}
实战案例
排序:
$heap = new MaxHeap();
$heap->insert(10);
$heap->insert(5);
$heap->insert(15);
$heap->insert(8);
$heap->insert(12);
while ($heap->size > 0) {
echo $heap->extractMax() . " ";
}
输出:15 12 10 8 5
优先级队列:
$heap = new MaxHeap();
$heap->insert(5);
$heap->insert(2);
$heap->insert(3);
$heap->insert(1);
while ($heap->size > 0) {
$element = $heap->extractMax();
echo "服务于元素 " . $element . "n";
}
输出:
服务于元素 5
服务于元素 3
服务于元素 2
服务于元素 1