堆排序php实现

xiaoxiao2021-02-28  37

作为一种可以使用数组实现的数据结构,使用php来模拟优先队列(堆排序)还是比较容易的。下面是我们的实现代码,其中insert使用的是上滤,delete使用的是下滤。我们模拟实现了最小堆和最大堆。

当然,php的spl库提供了类似的数据结构,它们基于c实现,在时间和空间上应该优于我们直接基于php的实现,大家可以参考下: 最小堆:http://php.net/manual/zh/class.splminheap.php 最大堆:http://php.net/manual/zh/class.splmaxheap.php

GitHub源码


<?php header('content-type:text/html;charset=utf-8'); /* * 堆排序,我们使用数组构建堆,注意数组下标从1开始。 */ abstract class Heap { protected $heap = [0]; protected $size = 0; public function __construct(array $dataList = []) { foreach ($dataList as $value) { $this->size++; $this->insert($value); } } //上滤法 abstract public function insert($value); //下滤法 abstract public function delete(); public function sort() { $result = []; $size = $this->size; for ($i = 1; $i <= $size; $i++) { $result[] = $this->delete(); } return $result; } } //最小堆 class MinHeap extends Heap { public function insert($value) { for ($i = $this->size; ($i > 0) && ($this->heap[floor($i/2)] > $value); $i = floor($i/2)) { $this->heap[$i] = $this->heap[floor($i/2)]; } $this->heap[$i] = $value; } public function delete() { $minValue = $this->heap[1]; $lastValue = $this->heap[$this->size--]; $child = 1; for ($i = 1; $i*2 <= $this->size; $i = $child) { $child = $i * 2; $leftIndex = $child; $rightIndex = $child + 1; if (($child != $this->size) && ($this->heap[$leftIndex] > $this->heap[$rightIndex])) { $child++; } if ($lastValue > $this->heap[$child]) { $this->heap[$i] = $this->heap[$child]; } else { break; } } $this->heap[$i] = $lastValue; return $minValue; } } //最大堆 class MaxHeap extends Heap { public function insert($value) { for ($i = $this->size; (floor($i/2) > 0) && ($this->heap[floor($i/2)] < $value); $i = floor($i/2)) { $this->heap[$i] = $this->heap[floor($i/2)]; } $this->heap[$i] = $value; } public function delete() { $maxValue = $this->heap[1]; $lastValue = $this->heap[$this->size--]; $child = 1; for ($i = 1; $i * 2 <= $this->size; $i = $child) { $child = $i * 2; $leftIndex = $child; $rightIndex = $child + 1; if (($child != $this->size) && ($this->heap[$leftIndex] < $this->heap[$rightIndex])) { $child++; } if ($this->heap[$child] > $lastValue) { $this->heap[$i] = $this->heap[$child]; } else { break; } } $this->heap[$i] = $lastValue; return $maxValue; } } class Test { public function run() { $testData = [33, 4, 3, 2, 5, 6, 9, 10, 32, 23, 45, 11, 25]; $minHeap = new MinHeap($testData); $maxHeap = new MaxHeap($testData); var_dump($minHeap->sort()); var_dump($maxHeap->sort()); } } $test = new Test(); $test->run();
转载请注明原文地址: https://www.6miu.com/read-2619607.html

最新回复(0)