В предыдущем сообщении в блоге описывалась реализация кучиВведение в кучи, сегодня в основном представлена куча индексов и оптимизация кучи индексов.
Что такое индексная куча?
Куча индексов оптимизирована для кучи.
Что оптимизировано?
В куче процессы создания кучи, вставки и удаления требуют большого количества операций подкачки. В предыдущей реализации операция подкачки заключалась в том, чтобы напрямую поменять местами два элемента в массиве данных. Куча индексов меняет местами индексы этих двух элементов, а не меняет местами элементы напрямую.
какая польза?
Есть два основных преимущества:
- Уменьшите стоимость операций SWAP, особенно для объектов, которые требуют много ресурсов для замены элементов, таких как большие строки.
- Элементы можно найти на основе их исходного положения, даже если элемент изменил положение.
Как?
Куча индексов использует новый массив типа int для хранения информации индекса. Часть кода выглядит следующим образом:
// 属性
$data = array();// 存放数据的数组 datas[1..n]
$indexes = array(); // 索引数组
Какая информация хранится в массиве индексов здесь? Как это работает? Предположим, у нас есть такая мини-куча:
Тогда представление массива:
datas: [-, 1, 15, 20, 34, 7]
Теперь, чтобы сохранить порядок минимальной кучи, необходимо поменять местами два элемента 15 и 7. Массив элементов после замены:
datas: [-, 1, 7, 20, 34, 15]
Сейчас мы хотим найти исходный элемент в позиции datas[2], но не можем его найти. Потому что data[2] был заменен на 7 в это время, и система не записывает, где заменено 15.
Можно ли сохранить исходные характеристики $data (читай O(1)) и получить элемент в позиции i, только напрямую datas[i], а также сохранить характеристики кучи. Да, используйте индексированную кучу.
Использовать кучу индексов
После использования кучи индексов инициализация двух массивов должна выглядеть так:
$datas: [-, 1, 15, 20, 34, 7]
$indexes: [-, 1, 2, 3, 4, 5]
На данный момент мы меняем местами индексы 2 и 5 в массиве индексов, не манипулируя массивом данных. После замены два массива выглядят так:
$datas: [-, 1, 15, 20, 34, 7]
$indexes: [-, 1, 5, 3, 4, 2]
В настоящее время, если вы хотите получить элемент в позиции i, вам нужно
indexes[i]] для получения.
Код:
<?php
// require('../Library/SortTestHelper.php');
require('../SortingAdvance/QuickSort.php');
/**
* 索引堆
*/
class IndexMaxHeap{
private $data;
private $count;
private $indexes;
public function __construct(){
$this->data = array();
$this->indexes = array();
$this->count = 0;
}
// public function __construct($arr){
// }
public function insert($item){
//从1开始
$this->data[$this->count + 1] = $item;
$this->indexes[$this->count + 1] = $item;
$this->_shiftUp($this->count+1);
$this->count++;
}
public function extractMax(){
$ret = $this->data[$this->indexes[1]];
swap( $this->indexes, 1 , $this->count);
$this->count--;
$this->_shiftDown(1);
return $ret;
}
/**
* [extractMaxIndex 让外界感觉从0开始]
* @return [type] [description]
*/
public function extractMaxIndex(){
$ret = $this->indexes[1] - 1;
swap( $this->indexes, 1 , $this->count);
$this->count--;
$this->_shiftDown(1);
return $ret;
}
public function getMaxIndex(){
return $this->indexes[1] - 1;
}
public function getMax(){
return $this->data[1];
}
public function isEmpty(){
return $this->count == 0;
}
public function getData(){
return $this->data;
}
/**
* [change 修改一个元素的值]
* @param [type] $i [description]
* @param [type] $newItem [description]
* @return [type] [description]
*/
public function change( $i , $newItem ){
$i += 1;
$this->data[$i] = $newItem;
// 找到indexes[j] = i, j表示data[i]在堆中的位置
// 之后shiftUp(j), 再shiftDown(j)
for( $j = 1 ; $j <= $this->count ; $j ++ ){
if( $this->indexes[$j] == $i ){
shiftUp($j);
shiftDown($j);
return;
}
}
}
/**
* [_shiftUp 新加入到堆中的元素直接放在数组后面，再与父元素比较后交换位置，直到根节点]
* @param [type] $k [description]
* @return [type] [description]
*/
private function _shiftUp($k){
//如果叶子节点的值比父元素大交换位置，并更新k的值
while( $k > 1 && $this->data[$this->indexes[(int)($k/2)]] < $this->data[$this->indexes[$k]] ){
// swap( $this->data[(int)($k/2)], $this->data[$k] );
swap( $this->indexes, (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[$this->indexes[$j+1]] > $this->data[$this->indexes[$j]] ) $j ++;
if( $this->data[$this->indexes[$k]] >= $this->data[$this->indexes[$j]] ) break;
// swap( $this->data[$k] , $this->data[$j] );
swap( $this->indexes, $k , $j );
$k = $j;
}
}
}
function heapSortUsingIndexMaxHeap($arr, $n){
$indexMaxHeap = new IndexMaxHeap();
for( $i = 0 ; $i < $n ; $i ++ ){
$indexMaxHeap -> insert($arr[$i] );
}
print("形成大根索引堆后， 从大大小输出为：\n");
for( $i = $n-1 ; $i >= 0 ; $i -- ){
// $arr[$i] = $indexMaxHeap -> extractMax();
$tmp = $indexMaxHeap -> extractMax();
print($tmp."\n");
}
}
$n = 10;
$arr = generateRandomArray($n, 0, $n);
print_r("生成的元素数组为：\n");
print_r( $arr);
$arr = heapSortUsingIndexMaxHeap($arr, $n);
?>
Результаты теста:
生成的元素数组为：
Array
(
[0] => 5
[1] => 7
[2] => 3
[3] => 2
[4] => 1
[5] => 6
[6] => 6
[7] => 3
[8] => 7
[9] => 9
)
形成大根索引堆后， 从大大小输出为：
7
7
6
6
6
6
5
3
3
1
обратный индекс
Следуя приведенному выше случаю, теперь мы можем получить данные, подобные этому: после сортировки arr второе по величине число
arr[indexes[1]]
А теперь такое требование: я хочу знать, где находится i-я позиция в исходном массиве arr после сортировки. То, что должно быть сделано?
Обычный способ - перебрать массив индексов следующим образом:
for( $j = 1 ; $j <= $this->count ; $j ++ ){
if( $this->indexes[$j] == $i ){
shiftUp($j);
shiftDown($j);
return;
}
}
Эта сложность в худшем случае O(N);
Так есть ли способ улучшить производительность?
Да, то есть снова использовать массив в обратном порядке в качестве обратного индекса. Данные, хранящиеся в обратном индексе, обычно выглядят так:
reverses[i] == j
indexes[j] == i
А затем вывести:
reverses[indexes[i]] = i;
indexes[reverses[i]] = i;
См. этот пример:
индексы[1] = 10; И reverses[1] хранит позицию индекса 1 со значением 10 в массиве индексов, а его значение равно 8, есть reverses[1] = 8; представляет 8-е место в индексном массиве
Обслуживание инвертированных индексов
Хотя использование инвертированного индекса в некоторых случаях повышает эффективность запросов, оно усложняет программу. Потому что этот массив сохраняется во время вставки и удаления.
Главная мысль
Основная идея заключается в следующем: независимо от операции должны сохраняться свойства массива индексов и обратного массива.
Некоторые проблемы, связанные с кучей
Реализация приоритетной очереди с использованием кучи
- Динамически выбирать задачу с наивысшим приоритетом для выполнения
Подобно управлению процессами операционной системы: используйте кучу, чтобы каждый раз находить процесс с наивысшим приоритетом для выполнения.Если приходит новый процесс, просто вставляйте его в кучу.Если вам нужно изменить приоритет процесса, вы нужно только использовать функцию изменения, чтобы изменить его.
- Выберите, кого атаковать в игре
Вы можете поместить врагов, которых нужно атаковать, в кучу, и использовать кучу, чтобы выбрать врагов, которых нужно атаковать больше всего. Вставляется в кучу, если входит новый враг.
-
Выберите 100 лучших из 1 миллиона элементов (выберите M лучших элементов из N элементов)
- Мы можем использовать алгоритм быстрой сортировки для сортировки, сложность которого составляет: O(n*logN)
- Использование очереди с приоритетом: O(NlogM)
- Используйте минимальную кучу, чтобы гарантировать, что элементы этой кучи каждый раз не превышают 100; изначально в эту кучу помещается 100 элементов, чтобы сформировать минимальную кучу, и каждый раз, когда элемент добавляется позже, наименьший элемент удаляется первым. , а затем добавляется новый. Элементы (необходимо поддерживать структуру кучи, сложность - O (logN), проходить каждый последующий элемент до последнего элемента и, наконец, образуют кучу из 100 элементов, которые будут самыми большими 100 элементами из 1 миллиона элементов.
-
многосторонняя сортировка слиянием
* merge的时候，将各个分割的字块的第一个元素形成一个最小堆，每次取堆顶元素进行merge
* 如果n个元素进行n路归并，其实归并算法就成了，堆排序算法。
- многомерная куча
Оптимизация деталей реализации кучи
- Замените операцию подкачки операцией копирования в shiftup и shiftDown.
------------------------- Великолепная разделительная линия --------------------
Друзья, которые прочитали это, могут нажать «Нравится» / «Подписаться», ваша поддержка — самая большая поддержка для меня.
личный блогСтек томатной технологииа такжеДомашняя страница Наггетс
Если вы хотите узнать больше, обратите внимание на мой публичный аккаунт WeChat: Tomato Technology Stack.