В основном введите приоритетную очередь, выведите кучу через приоритетную очередь, а затем напишите класс (php-код), чтобы реализовать большую корневую кучу
Пожалуйста, посетите мой блог для оригинального текстаСтек томатной технологии
приоритетная очередь
определение
Очередь с приоритетом — это абстрактный тип данных в информатике. Каждый элемент в очереди приоритетов имеет свой собственный приоритет, и элемент с наивысшим приоритетом обслуживается первым, элементы с одинаковым приоритетом обслуживаются в соответствии с их порядком в очереди приоритетов. Очереди с приоритетом часто реализуются с использованием кучи.
Функции
- Обычная очередь: первый пришел, первый вышел, последний пришел, последний вышел
- Приоритетная очередь: порядок удаления из очереди не имеет ничего общего с порядком постановки в очередь, но связан с приоритетом.
практическое использование
- Центр обработки динамических задач (операционная система)
Зачем использовать приоритетные очереди
вопрос
- Выберите 100 лучших из 1 000 000 элементов
- Выберите первые M элементов из N элементов
Решение
- Сортировка, временная сложность O(NlogN)
- Использование очередей с приоритетами: временная сложность (NlogM)
Сравнение реализации приоритетной очереди
куча
определение
Реализация кучи на самом деле является своего рода бинарным деревом путем построения бинарной кучи, в силу универсальности ее применения, когда она не ограничена, она относится к этой реализации структуры данных. Эта структура данных имеет следующие свойства.
- Любой узел меньше (или больше) всех своих потомков, а элемент min (или max) находится в корне кучи (упорядочение кучи).
- Куча всегда является полным деревом. То есть, кроме нижнего слоя, узлы других слоев заполняются элементами, а нижний слой заполняется максимально слева направо.
- Куча с наибольшим корневым узлом называется максимальной кучей или большой корневой кучей, а куча с наименьшим корневым узлом называется минимальной кучей или малой корневой кучей. Общие кучи включают бинарные кучи, кучи Фибоначчи и т. д.
Хранение двоичных куч с помощью массивов
Код
<?php
require('../Library/SortTestHelper.php');
/**
* 最大堆
*/
class MaxHeap{
private $data;
private $count;
public function __construct(){
$this->data = array();
$this->count = 0;
}
// public function __construct($arr){
// }
public function insert($item){
//从1开始
$this->data[$this->count + 1] = $item;
$this->_shiftUp($this->count+1);
$this->count++;
}
public function extractMax(){
$ret = $this->data[1];
swap( $this->data, 1 , $this->count);
$this->count--;
$this->_shiftDown(1);
return $ret;
}
public function getMax(){
return $this->data[1];
}
public function isEmpty(){
return $this->count == 0;
}
public function getData(){
return $this->data;
}
/**
* [_shiftUp 新加入到堆中的元素直接放在数组后面，再与父元素比较后交换位置，直到根节点]
* @param [type] $k [description]
* @return [type] [description]
*/
private function _shiftUp($k){
//如果叶子节点的值比父元素大交换位置，并更新k的值
while( $k > 1 && $this->data[(int)($k/2)] < $this->data[$k] ){
// swap( $this->data[(int)($k/2)], $this->data[$k] );
swap( $this->data, (int)($k/2) , $k);
$k = (int)($k/2);
}
}
/**
* [_shiftDown 元素出堆的时候，需要维护此时的堆依然是一个大根堆， 此时将数组元素的最后一个值与第一个值交换，后从上往下维护堆的性质]
* @param [type] $k [description]
* @return [type] [description]
*/
private function _shiftDown($k){
//2k代表该节点的左子节点
while( 2*$k <= $this->count ){
$j = 2*$k;
//判断右节点是否存在，并且右节点大于左节点
if( $j+1 <= $this->count && $this->data[$j+1] > $this->data[$j] ) $j ++;
if( $this->data[$k] >= $this->data[$j] ) break;
// swap( $this->data[$k] , $this->data[$j] );
swap( $this->data, $k , $j );
$k = $j;
}
}
}
$head_obj = new MaxHeap();
$n = 10;
for ($i=0; $i < $n; $i++) {
$head_obj -> insert(rand(0, 1000));
}
print_r($head_obj -> getData());
while (!$head_obj -> isEmpty()) {
echo $head_obj -> extractMax()."\n";
}
?>
результат
生成的堆为：
Array
(
[1] => 916
[2] => 776
[3] => 590
[4] => 615
[5] => 764
[6] => 539
[7] => 95
[8] => 167
[9] => 23
[10] => 374
)
打印大根堆为：
916
776
764
615
590
539
374
167
95
23
------------------------- Великолепная разделительная линия --------------------
Друзья, которые прочитали это, могут нажать «Нравится» / «Подписаться», ваша поддержка — самая большая поддержка для меня.
личный блогСтек томатной технологииа такжеДомашняя страница Наггетс
Если вы хотите узнать больше, обратите внимание на мой публичный аккаунт WeChat: Tomato Technology Stack.