Интервью с PHP: что такое куча и сортировка кучей?

интервью задняя часть PHP алгоритм

Что такое куча?

Куча — это специальная структура данных, основанная на абстрактном типе данных дерева и используемая во многих алгоритмах и структурах данных. Типичным примером являются приоритетные очереди и пирамидальная сортировка, один из алгоритмов сортировки. В этой статье мы обсудим свойства кучи, различные типы кучи и Общие операции с кучей. Также мы изучим сортировку кучей и реализуем сортировку кучи с помощью SPL.

По определению куча — это древовидная структура данных со свойствами кучи. Если родительский узел больше дочернего узла, то он называется максимальной кучей, если родительский узел меньше дочернего узла, он называется минимальной кучей. На следующем рисунке показан пример максимальной кучи

clipboard.png

Смотрим на корневой узел, значение 100 больше, чем у двух дочерних узлов 19 и 36. Для 19 значение больше, чем 17 и 3. Те же правила применяются к другим узлам. Как видим, дерево не полностью отсортировано. Но важным фактом является то, что мы всегда можем найти максимум или минимум дерева, что очень полезно во многих частных случаях.

Существует много стеков, таких как бинарный, стопка B, Фибоначчи, стопка трех юаней, стопка дерева, слабая куча и т. д. Связка из двух вилок является самой популярной в куче. Five-fork — это полное бинарное дерево (друзья, которые не понимают бинарное дерево, могут посмотреть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), то есть получение максимального или минимального значения. Я смотрю на анализ сложности бинарной кучи.

действовать средняя сложность худшая сложность
Search O(n) O(n)
Insert O(1) O(log n)
Delete O(log n) O(log n)
Extract O(1) O(1)

Поскольку двоичная куча не отсортирована полностью, операция поиска займет больше времени, чем двоичное дерево поиска.

Куча и приоритетная очередь

Одной из наиболее распространенных операций является использование кучи в качестве приоритетной очереди. существуетСтек 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). По сравнению с сортировкой слиянием сортировка кучей имеет лучшую производительность.

SplHeap, SplMinHeap и SplMaxHeap в PHP

Конечно, удобная встроенная стандартная библиотека PHP помогла мне добиться кучи, которую можно передатьSplHeap,SplMinHeap,SplMaxHeapиспользовать их.

больше контента

Каталог тем серии базовых данных PHP:адрес. Он в основном использует синтаксис PHP для обобщения основных структур данных и алгоритмов. Есть также базовые знания, которые легко игнорировать в нашей повседневной разработке PHP, и некоторые практические предложения по спецификации, развертыванию и оптимизации в современной разработке PHP, а также углубленное исследование характеристик языка Javascript.

Категории