堆是什么？堆是一种基于树抽象数据类型的特殊数据结构，被用于许多算法和数据结构中。一个常见的例子是优先队列，其中一种排序算法是堆排序。在这篇文章中，我们将讨论堆的属性、不同类型的堆以及堆上的常见操作。我们还将学习堆排序并将使用SPL实现堆。根据定义，堆是具有堆属性的树状数据结构。如果父节点大于子节点，则称为最大堆，如果父节点小于子节点，则称为最小堆。下图是最大堆的例子。我们看根节点，100的值大于19和36这两个子节点。对于19，这个值大于17和3。同样的规则也适用于其他节点。正如我们所看到的，树没有完全排序。但重要的是，我们总能找到树的最大值或最小值，这在许多特殊情况下非常有用。堆结构有很多种，如二叉堆、B堆、斐波那契堆、三元堆、树堆、弱堆等，二叉堆是最流行的堆实现类型。二叉堆是一棵完全二叉树（不懂二叉树的朋友可以看PHP实现二叉树），树的内部所有结点都被完全填充，最后一层可以完全填充也可以部分填充。对于二叉堆，我们可以以对数时间复杂度执行大多数操作。堆操作堆是一种特殊的树状数据结构。我们首先根据给定的数据构建堆。由于堆有严格的构造规则，所以我们操作的每一步都必须满足这个规则。下面是堆的一些核心操作。创建堆插入新值从堆中提取最小值或最大值删除值交换从给定的一组项目或数字创建堆需要我们确保满足堆规则和二叉树属性。这意味着父节点必须大于或小于子节点。树中的所有节点都需要遵守此规则。此外，树必须是完全二叉树。创建堆时，我们从一个节点开始，向堆中插入一个新节点。在插入节点操作时，我们不能从任意一个节点开始。插入操作如下在堆底插入一个新节点检查新节点和父节点的大小顺序，如果顺序正确，则停止。如果它们的顺序不正确，请交换它们并继续之前的检查。此步骤与前一步一起称为筛选或上升等。获取操作（最小或最大）从堆中获取根节点。在此之后，我们必须执行以下操作，以确保剩余的节点仍然符合堆的特性。将堆中的最后一个节点移出作为新的根节点将新的根节点与子节点进行比较，如果它们的顺序正确则停止。如果不是，将根节点与子节点交换（小根堆时最小子节点，大根堆时最大子节点），继续前面的步骤。这一步与上一步一起称为下堆。在堆中，一个重要的操作是交换。现在我们将使用PHP7来实现二叉堆。命名空间DataStructure\Heap;classMaxHeap{public$heap;公共$计数；publicfunction__construct(int$size){//初始化堆$this->heap=array_fill(0,$size,0);$this->count=0;}publicfunctioncreate(array$arr=[]){array_map(function($item){$this->insert($item);},$arr);}publicfunctioninsert(int$data){//插入数据操作if($this->count==0){//插入第一条数据$this->heap[0]=$data;$this->count=1;}else{//new插入的数据放在堆的末尾$this->heap[$this->count++]=$data;//向上浮动到合适的位置$this->siftUp();}}publicfunctiondisplay(){returnimplode("",array_slice($this->heap,0));}publicfunctionsiftUp(){//待上浮元素的临时位置$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);}}publicfunctionswap(int$a,int$b){$temp=$this->heap[$a];$this->heap[$a]=$this->heap[$b];$this->heap[$b]=$temp;}publicfunctionextractMax(){//最大值为堆的第一个值$max=$this->heap[0];//提取堆中最后一个元素$this->heap[0]=$this->heap[$this->count-1];//将最后一个节点重置为0$this->heap[--$this->count]=0;//将根节点下沉到合适的位置$this->siftDown(0);返回$最大值；}publicfunctionsiftDown(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)，就是获取最大值或者最小值.下面我来看一下二叉堆的复杂度分析。操作的平均复杂度是最差复杂度SearchO(n)O(n)InsertO(1)O(logn)DeleteO(logn)O(logn)ExtractO(1)O(1)因为二叉堆是不是完全排序的，所以搜索操作会比二叉搜索树花费更多的时间。堆和优先队列最常见的操作之一是将堆用作优先队列。在PHP实现栈和PHP实现队列中，我们了解到优先级队列是一种根据元素权重而不是入队顺序进行出队操作的结构。我们已经用链表实现了优先队列和用Spl实现了优先队列，现在我们用堆实现了优先队列。命名空间DataStructure\Heap;classPriorityQueueextendsMaxHeap{publicfunction__construct(int$size){parent::__construct($size);}publicfunctionenqueue(int$val){parent::insert($val);}publicfunctiondequeue(){returnparent::extractMax();}}堆排序??在堆排序中，我们需要用给定的值构建一个堆。然后不断的检查堆的值，保证随时对整个堆进行排序。在正常的堆结构中，每次将新值插入适当的位置时我们都会停止检查，但在堆排序中，只要有下一个值，我们就会继续检查构建堆。伪代码如下：HeapSort(A)BuildHeap(A)fori=n-1to0swap(A[0],A[i])n=n-1Heapify(A,0)BuildHeap(A)n=elemens_in(A)fori=floor(n/2)to0Heapify(A,i)Heapify(A,i)left=2i+1;right=2i+2;max=iif(left
