最新公告
  • 欢迎您光临码农资源网,本站秉承服务宗旨 履行“站长”责任,销售只是起点 服务永无止境!加入我们
  • PHP数据结构:堆数据结构的奥妙,实现高效的排序与优先级队列

    php 中的堆数据结构是一种满足完全二叉树和堆性质(父结点值大于/小于子结点值)的树状结构,使用数组实现。堆支持两种操作:排序(从小到大提取最大元素)和优先级队列(根据优先级提取最大元素),分别通过 heapifyup 和 heapifydown 方法维护堆的性质。

    PHP数据结构:堆数据结构的奥妙,实现高效的排序与优先级队列

    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

    想要了解更多内容,请持续关注码农资源网,一起探索发现编程世界的无限可能!
    本站部分资源来源于网络,仅限用于学习和研究目的,请勿用于其他用途。
    如有侵权请发送邮件至1943759704@qq.com删除

    码农资源网 » PHP数据结构:堆数据结构的奥妙,实现高效的排序与优先级队列
    • 5会员总数(位)
    • 21779资源总数(个)
    • 648本周发布(个)
    • 0 今日发布(个)
    • 171稳定运行(天)

    提供最优质的资源集合

    立即查看 了解详情