二叉堆笔记

May 22nd, 2020

介绍

一个小顶堆(或大顶堆)是一个完整的二叉树。其中每个节点都小于其子节点。因此，根是树中的最小元素。

图-2

在最小堆中有两个关键操作：insert和extract_min。

插入操作

当我们向一个最小堆插入元素时，总是从底部开始。从最右边的节点开始插入操作以保持树的完整性。然后，通过与其祖先节点进行交换来“修复”树，直到找到新元素的适当位置。我们基本上是在向上传递最小的元素

图-1

提取最小元素

找到小顶堆的最小元素是小菜一碟：它总是在顶部。颇为棘手的是如何删除该元素（其实也不是那么棘手）。首先，删除最小元素并将其与堆中的最后一个元素（位于最底层、最右边的元素）进行交换。然后，向下传递这个元素，不断使其与自身子节点之一进行交换，直到小顶堆的属性得以恢复。是和左边的孩子节点还是右边的孩子节点进行交换取决于它们的值。左右元素之间没有固定的顺序，但是为了保持小顶堆的元素有序，你需要选择两者中较小的元素。

图-3

堆的基本操作

堆的几个基本操作都依赖于两个重要的函数siftUp和siftDown，堆的insert通常是在堆尾插入新元素并siftUp调整堆，而extractMin是在删除堆顶元素，然后将最后一个元素放置堆顶并调用siftDown调整堆。 堆得基本操作的时间复杂度如下表所示：

  • heapify O(N)
  • insert O(logN)
  • extractMin O(logN)
  • delete O(logN)
  • peek O(1)

总结

  • （1）堆是一颗完全二叉树；
  • （2）小（大）顶堆中的每一个节点都不小于（不大于）它的父节点；
  • （3）堆的插入、删除元素的时间复杂度都是O(log n)；
  • （4）建堆的时间复杂度是O(n)；
  • （5）堆排序的时间复杂度是O(nlog n)；
  • （6）堆排序的空间复杂度是O(1)；

代码

最小堆代码示例:

<?php

class Heap
{

    private $items;
    private $size;
    private $length;

    public function __construct($length)
    {
        $this->items = [];
        $this->size = 0;
        $this->length = $length;
    }

    public function peek()
    {
        return $this->items[0]??null;
    }

    public function insert($value)
    {
        if ($this->size == $this->length) {
            return false;
        }
        $this->items[$this->size] = $value;
        $this->shitUp($this->size);
        $this->size++;
        return true;
    }

    public function extractMin()
    {
        $min = $this->peek();
        if (null == $min) {
            return $min;
        }

        $this->items[0] = $this->items[$this->size-1];

        $this->size--;
        unset($this->items[$this->size]);

        $this->shitDown(0);

        return $min;
    }

    private function shitUp($pos)
    {
        if (0 == $pos) {
            return;
        }

        if ($pos&1) {
            $parentPos = ($pos-1)/2;
        } else {
            $parentPos = ($pos-2)/2;
        }

        if ($this->items[$pos] < $this->items[$parentPos]) {
            list($this->items[$pos], $this->items[$parentPos]) = [
                $this->items[$parentPos],
                $this->items[$pos],
            ];
            $this->shitUp($parentPos);
        }
    }

    private function shitDown($pos)
    {
        $left = $pos * 2 + 1;
        $right = $pos * 2 + 2;
        $mpos = $pos;
        if (!empty($this->items[$left]) && $this->items[$left] < $this->items[$pos]) {
            $mpos = $left;
        }
        if (!empty($this->items[$right]) && $this->items[$right] < $this->items[$mpos]) {
            $mpos = $right;
        }

        if ($mpos != $pos) {
            list($this->items[$pos], $this->items[$mpos]) = [
                $this->items[$mpos],
                $this->items[$pos],
            ];
            $this->shitDown($mpos);
        }
    }

    public function display()
    {
        $this->_display(0, 0);
    }

    private function _display($root, $layout)
    {
        if (empty($this->items[$root])) {
            return;
        }

        echo str_repeat("\t", $layout). $this->items[$root], PHP_EOL;

        $left = $root*2 +1;
        $right = $root*2 + 2;
        $layout += 1;

        if (!empty($this->items[$left])) {
            $this->_display($left, $layout);
        }

        if (!empty($this->items[$right])) {
            $this->_display($right, $layout);
        }
    }

    public static function main()
    {
        $heap = new self(10);
        foreach ([1, 3, 5, 4, 8, 9, 10] as $value) {
            $heap->insert($value);
        }

        echo '遍历显示堆', PHP_EOL;
        $heap->display();

        echo "peek", PHP_EOL;
        echo $heap->peek(), PHP_EOL;

        echo "extractMin", PHP_EOL;
        echo $heap->extractMin(), PHP_EOL;
        echo $heap->extractMin(), PHP_EOL;
        echo $heap->extractMin(), PHP_EOL;

        echo "peek", PHP_EOL;
        echo $heap->peek(), PHP_EOL;

        echo "extractMin", PHP_EOL;
        echo $heap->extractMin(), PHP_EOL;
        echo $heap->extractMin(), PHP_EOL;

        echo '遍历显示堆', PHP_EOL;
        $heap->display();
    }
}

Heap::main();

运行结果:


遍历显示堆
1
        3
                4
                8
        5
                9
                10
peek
1
extractMin
1
3
4
peek
5
extractMin
5
8
遍历显示堆
9
        10

二叉堆排序代码如下:

<?php

class HeapSort
{
    private $items;

    public function __construct(array $items)
    {
        $this->items = $items;
    }

    public function sort()
    {
        $arrLen = count($this->items);
        $this->buildMaxHeap($arrLen);

        for ($i = $arrLen-1; $i >= 0; $i--) {
            list($this->items[0], $this->items[$i]) = [
                $this->items[$i],
                $this->items[0]
            ];

            $arrLen -= 1;
            $this->heapify(0, $arrLen);
        }

        return $this->items;
    }

    private function buildMaxHeap($arrLen)
    {
        for ($i = intval($arrLen/2); $i >= 0; $i--) {
            $this->heapify($i, $arrLen);
        }
    }

    private function heapify($i, $arrLen)
    {
        $left = 2 * $i + 1;
        $right = 2 * $i + 2;
        $largest = $i;

        if ($left < $arrLen && $this->items[$left] > $this->items[$largest]) {
            $largest = $left;
        }
        if ($right < $arrLen && $this->items[$right] > $this->items[$largest]) {
            $largest = $right;
        }
        if ($largest != $i) {
            list($this->items[$i], $this->items[$largest]) = [
                $this->items[$largest],
                $this->items[$i]
            ];
            $this->heapify($largest, $arrLen);
        }
    }

    public static function main()
    {
        $items = [
            1,
            5,
            3,
            6,
            2,
            7,
            4,
        ];
        echo '排序前', PHP_EOL;
        var_dump($items);

        $self = new self($items);
        echo '排序后', PHP_EOL;
        var_dump($self->sort());

    }
}

HeapSort::main();

运行结果:

/usr/local/opt/php@7.1/bin/php /Users/martin/heapsort.php
排序前
/Users/martin/heapsort.php:70:
array(7) {
  [0] =>
  int(1)
  [1] =>
  int(5)
  [2] =>
  int(3)
  [3] =>
  int(6)
  [4] =>
  int(2)
  [5] =>
  int(7)
  [6] =>
  int(4)
}
排序后
/Users/martin/heapsort.php:74:
array(7) {
  [0] =>
  int(1)
  [1] =>
  int(2)
  [2] =>
  int(3)
  [3] =>
  int(4)
  [4] =>
  int(5)
  [5] =>
  int(6)
  [6] =>
  int(7)
}

延伸

  • 优先队列
  • 堆排序
  • 海量实数中（一亿级别以上）找到TopK（一万级别以下）的数集合。

参考

  • https://blog.csdn.net/u014532901/article/details/78573556
  • https://zhuanlan.zhihu.com/p/78146654

JY