PHP面试问答题：什么是堆和堆排序？

什么是希望？

堆是一种基于树抽象数据类型的特殊数据结构，在许多算法和数据结构中都有使用。一个常见的例子是优先级队列，以及堆排序（排序算法之一）。在本文中，我们讨论堆的属性、不同类型的堆以及常见的堆操作。另外，我们还学习了堆排序，并使用SPL实现堆。

根据定义，堆是一种具有堆特性的树形数据结构。如果父节点大于子节点，则称为最大堆；如果父节点小于子节点，则称为最小堆。下图是最大堆的示例

我们来看看根节点。值 100 大于两个子节点 19 和 36。对于 19，该值大于 17 和 3。相同的规则适用于其他节点。我们可以看到树没有完全排序。但重要的事实是，我们总能找到树的最大值或最小值，这对于许多特殊来说非常有用。

堆结构有很多种，例如二元堆、B堆、斐波那契堆、三元堆、树堆、弱堆等。二元堆是最流行的堆实现。二叉堆就是一棵完全二叉树（不懂二叉树的朋友可以看PHP实现二叉树）。树的所有内部节点都被完全填充，最后一层可以被完全或部分填充。使用二叉堆，我们可以以对数时间复杂度执行大多数操作。

堆操作

堆是一种特殊的树形数据结构。我们首先根据给定的数据构建堆。因为希望有严格的施工规定，所以我们的每一步操作都必须遵守这个规定。下面是堆的一些核心活动。

• 创建堆
• 插入新值
• 从堆中提取最小值或最大值
• 删除值
• 交换

从给定的项目或数字集合创建堆我们的工作是确保满足堆规则和二叉树属性。这意味着父节点必须大于或小于子节点。树中的所有节点都必须遵循此规则。同样，该树必须是完全二叉树。当我们创建堆时，我们从一个节点开始并向堆中添加一个新节点。

插入节点操作时，我们不能从任何节点开始。插入操作如下：

• 将新节点插入堆底
• 检查新节点与其父节点的大小顺序，如果顺序正确则停止。
• 如果顺序不正确，请交换它们并从上一步继续检查。这一步与上一步一起称为筛选或提升等。

提取操作（min 或 max）是从堆中删除根节点。之后，我们需要执行以下操作以确保剩余节点仍然满足堆的特性。

• 将堆的最后一个节点移动为新的根。
• 将新的根节点与子节点进行比较，当它们的顺序正确时停止。
• 如果不是，则将根节点与子节点交换（小根堆则交换最小子节点，大根堆则交换最大子节点），然后继续前面的步骤。这一步与上一步一起称为降低堆栈。

希望，兑换是一项重要的操作。现在我们将使用PHP7来实现二进制堆。

namespace DataStructure\Heap;

class MaxHeap
{
    public $heap;
    public $count;

    public function __construct(int $size)
    {
        //初始化堆
        $this->heap = array_fill(0, $size, 0);
        $this->count = 0;
    }

    public function create(array $arr = [])
    {
        array_map(function($item){
            $this->insert($item);
        }, $arr);
    }

    public function insert(int $data)
    {
        //插入数据操作
        if ($this->count == 0) {
            //插入第一条数据
            $this->heap[0] = $data;
            $this->count = 1;
        } else {
            //新插入的数据放到堆的最后面
            $this->heap[$this->count++] = $data;
            //上浮到合适位置
            $this->siftUp();
        }
    }

    public function display()
    {
		return implode(" ", array_slice($this->heap, 0));
    }

    public function siftUp()
    {
        //待上浮元素的临时位置
        $tempPos = $this->count - 1;    
        //根据完全二叉树性质找到副节点的位置
        $parentPos = intval($tempPos / 2);

        while ($tempPos > 0 && $this->heap[$parentPos] < $this->heap[$tempPos]) {
            //当不是根节点并且副节点的值小于临时节点的值，就交换两个节点的值
            $this->swap($parentPos, $tempPos);
            //重置上浮元素的位置
            $tempPos = $parentPos;
            //重置父节点的位置
            $parentPos = intval($tempPos / 2);
        }
    }

    public function swap(int $a, int $b)
    {
        $temp = $this->heap[$a];
        $this->heap[$a] = $this->heap[$b];
        $this->heap[$b] = $temp;
    }

    public function extractMax()
    {
        //最大值就是大跟堆的第一个值
        $max = $this->heap[0];
        //把堆的最后一个元素作为临时的根节点
        $this->heap[0] = $this->heap[$this->count - 1];
        //把最后一个节点重置为0
        $this->heap[--$this->count] = 0;
        //下沉根节点到合适的位置
        $this->siftDown(0);

        return $max;
    }

    public function siftDown(int $k)
    {
        //最大值的位置
        $largest = $k;
        //左孩子的位置
        $left = 2 * $k + 1;
        //右孩子的位置
        $right = 2 * $k + 2;


        if ($left < $this->count && $this->heap[$largest] < $this->heap[$left]) {
            //如果左孩子大于最大值，重置最大值的位置为左孩子
            $largest = $left;
        }

        if ($right < $this->count && $this->heap[$largest] < $this->heap[$right]) {
            //如果右孩子大于最大值，重置最大值的位置为左孩子
            $largest = $right;
        }


        //如果最大值的位置发生改变
        if ($largest != $k) {
            //交换位置
            $this->swap($largest, $k);
            //继续下沉直到初始位置不发生改变
            $this->siftDown($largest);
        }
    }
}
复制代码

复杂度分析

因为不同类型的堆有不同的实现，所以不同的堆实现也有不同的复杂度。然而，在一些实现中存在复杂度为O(1)的堆操作，即获取最大值或最小值。我看一下二进制堆的复杂度分析。

因为二叉堆不完整Sorted ，因此搜索将比二叉搜索树花费更多时间。

堆和优先级队列

最常见的操作之一是将堆用作优先级队列。在PHP部署栈和PHP部署队列中，我们了解到优先级队列是一种根据元素的权重而不是元素的排队顺序来执行出队操作的结构。我们已经使用链表来实现优先级队列，使用Spl来实现优先级队列，现在我们使用堆来实现优先级队列。

namespace DataStructure\Heap;

class PriorityQueue extends MaxHeap
{
    public function __construct(int $size)
	{
		parent::__construct($size);
	}

	public function enqueue(int $val)
	{
		parent::insert($val);
	}

	public function dequeue()
	{
		return parent::extractMax();
	}
}
复制代码

堆排序

在堆排序中，我们必须使用给定的值构建一个堆。然后持续监控堆值，以确保整个堆始终处于排序状态。在普通的堆结构中，每次在正确的位置插入新值时，我们都会停止检查，但在堆排序中，只要有下一个值，我们就会继续检查构造堆。伪代码如下：

HeapSort(A)
BuildHeap(A)
for i = n-1 to 0
swap(A[0],A[i])
n = n - 1
Heapify(A, 0)

BuildHeap(A)
n = elemens_in(A)
for i = floor(n / 2) to 0
Heapify(A, i)

Heapify(A, i)
left = 2i+1;
right = 2i + 2;
max = i

if (left < n and A[left] > A[i])
max = left
if (right < n and A[right] > A[max])
max = right

if (max != i)
swap(A[i], A[max])
Heapify(A, max)
复制代码

从上面的伪代码可以看出，堆排序的第一步就是构建堆。每次我们向堆中添加一个新元素时，我们都会调用 heapify 来匹配堆的属性。堆构建完成后，我们检查所有元素并使用 PHP 实现堆排序。您可以在此处查看完整代码。

function heapSort(&$arr)
{
    $length = count($arr);
    buildHeap($arr);
    $heapSize = $length - 1;
    for ($i = $heapSize; $i >= 0; $i--) {
        list($arr[0], $arr[$heapSize]) = [$arr[$heapSize], $arr[0]];
        $heapSize--;
        heapify(0, $heapSize, $arr);
    }
}

function buildHeap(&$arr)
{
    $length = count($arr);
    $heapSize = $length - 1;
    for ($i = ($length / 2); $i >= 0; $i--) {
        heapify($i, $heapSize, $arr);
    }
}

function heapify(int $k, int $heapSize, array &$arr)
{
    $largest = $k;
    $left = 2 * $k + 1;
    $right = 2 * $k + 2;

    if ($left <= $heapSize && $arr[$k] < $arr[$left]) {
        $largest = $left;
    }

    if ($right <= $heapSize && $arr[$largest] < $arr[$right]) {
        $largest = $right;
    }

    if ($largest != $k) {
        list($arr[$largest], $arr[$k]) = [$arr[$k], $arr[$largest]];
        heapify($largest, $heapSize, $arr);
    }
}
复制代码

堆排序的时间复杂度为O(nlog n)，空间复杂度为O(1)。与归并排序相比，堆排序具有更好的性能。

PHP中的SplHeap、SplMinHeap和SplMaxHeap

当然，方便的内置PHP标准库帮我实现了堆，你可以通过SplHeap、SplMinHeap、 SplMaxHeap 使用它们。

作者：潇潇
链接：https://juejin.im/post/5b7964636fb9a01a1a27bb04
来源：掘金
版权归作者所有。商业转载请联系作者获得许可。非商业转载请注明出处。