структура данных двоичной кучи — это объект массива, который мы можем рассматривать как почти полное двоичное дерево, как показано на следующем рисунке.
обратите внимание, что каждый узел в дереве соответствует элементу массива
массив A, который представляет кучу, представляет собой объект с двумя атрибутами A.length, который представляет размер массива, и A.heapsize, который представляет, сколько элементов в куче хранится в массиве A.
то есть A[0….A.length] может содержать числа
только элементы в A[0…A.heapSize] являются допустимыми элементами кучи, корень дерева всегда в A[0]
учитывая индекс i узла, мы можем легко вычислить индексы левого и правого потомков
Левый ребенок (я) = 2 * (я + 1)
Правый ребенок = 2(i+1)+1
Родитель(я) = int((я+1)/2)
существует два вида кучи max-heaps и min-heaps, и в обоих типах значения удовлетворяют свойству кучи
для свойства max-heap является то, что для каждого узла i, отличного от корня A[Parent(i)≥A[i]]
это означает, что значение узла не больше значения родителя, поэтому самый большой элемент в максимальной куче - это корень, поддерево с корнем в узле содержит значения, не превышающие значения, содержащиеся в самом узле.
Минимальная куча организована противоположным образом: свойство минимальной кучи состоит в том, что для каждого узла i
А[Родительский[я]‹А[я]]
поэтому наименьший элемент хранится в корне
рассматривая кучу как дерево, мы определяем высоту узла в куче как количество ребер на самом длинном простом нисходящем пути от узла к листу, и мы определяем высоту кучи как высоту ее корня.
поскольку куча из n элементов основана на полном двоичном дереве, его высота (logn)
Поддержание свойства кучи
чтобы сохранить свойство максимальной кучи, мы вызываем процедуру Max-Heapify с входными данными в виде массива A и индексом i в массиве, когда он вызывается. Max-Heapify предполагает, что двоичные деревья с корнями слева (i) и справа (i) являются максимальными кучами
но это A [i] может быть меньше, чем его дочерние элементы, что нарушает свойство максимальной кучи, поэтому, когда мы вызываем Max-Heapify, A [i] плавает вниз в максимальной куче, так что поддерево, сгнившее в индексе i, подчиняется свойству максимальной кучи.
void Max_Heapify(int index){
int left = leftChild(index);
int right = RightChild(index);
int largest = index;
if(left<heap.size()&&heap[left]>heap[index]) largest = left;
else largest = index;
if(right<heap.size()&&heap[right]>heap[largest]) largest = right;
if(largest != index){
int tmp = heap[index];
heap[index] = heap[largest];
heap[largest] = tmp;
Max_Heapify(largest);
}
}
Создание кучи
мы можем использовать процедуру Max-Heapify снизу вверх для преобразования массива размера n в максимальную кучу
обратите внимание, что куча размера n все элементы в подмассиве A[(n/2+1)…..n] являются листьями дерева, поэтому каждый из них представляет собой кучу из 1 элемента
доказательство
- Итак, в основном в представлении кучи LEFT(i) относится к индексу i′s левого дочернего элемента. Мы хотим показать, что индекс ⌊n/2⌋+1 является листом, а не промежуточным узлом, что можно доказать, если мы сможем показать, что индекс левого дочернего элемента больше, чем количество элементов в куче. С другой стороны, LEFT(⌊n/2⌋+1)=2(⌊n/2 ⌋+1)=2⌊n/2⌋+2, и, удалив эти скобки вокруг n/2, мы можем показать, что оно больше 2( n/2−1)+2=n.
алгоритм
void BuildMaxHeap(){
for(int i = (heap.size()/2)-1;i>=0;i--){
Max_Heapify(i);
}
}
доказательство правильности
Чтобы показать, почему BuildMaxHeap работает правильно, мы используем следующий цикл
инвариант
В начале каждой итерации цикла for каждый узел i +1;
i+2,i+3 … n является корнем максимальной кучи
этап инициализации: до первой итерации цикла i = (n/2)-1 каждый узел n/2 , n/2 +1 ,n/2 +2 …… n-1 листовой узел и, следовательно, корень тривиальной максимальной кучи
поддерживать инвариант цикла: чтобы увидеть, что каждая итерация поддерживает инвариант цикла, обратите внимание, что все дочерние элементы узла i имеют номера выше, чем i , поэтому по инварианту цикла они оба являются корнями максимальной кучи, и это условие для использования MaxHeapify, чтобы сделать узел i максимальным корнем кучи
Продолжительность
мы можем вычислить простую верхнюю границу времени работы BuildMaxHeap следующим образом: мы знаем, что MaxHeapify равно O(n log n), и мы вызываем его O(n) раз, поэтому BuildMaxHeap имеет верхнюю границу O(n log n)
но мы можем найти более точную верхнюю границу, используя тот факт, что куча из n элементов имеет высоту log(n) и не более n/(2^h+1) узлов на высоте h
время, требуемое MaxHeapify при вызове на узле высоты h, равно O(h)
мы можем выразить время работы BuildMaxHeap следующим образом
Алгоритм сортировки кучей
Алгоритм сортировки кучи начинается с создания максимальной кучи, поскольку максимальный элемент хранится в A[0], мы можем обменять его на последний элемент A[n-1], а затем отбросить последний элемент из кучи, а затем вызвать MaxHeapify
static vector<int> heapSort(Heap h){
vector<int>sorted;
h.BuildMaxHeap();
for(int i = h.heap.size()-1;i>0;i--){
sorted.push_back(h.heap[0]);
h.heap[0] = h.heap[i];
h.heap.pop_back();
h.printHeap();
h.Max_Heapify(0);
}
return sorted;
}
процедура сортировки кучи занимает O (n log (n)) время выполнения, так как maxHeapify занимает O (log (n)) и выполняется n-1 раз
эффективная реализация Priority Queue с использованием кучи
приоритетная очередь — это структура данных для хранения набора значений, называемых ключами.
МаксимальныйЭлемент
возвращает элемент кучи с наибольшим ключом
int MaxElement(){return heap[0];}
ЭкстрактМакс
удаляет и возвращает элемент кучи с наибольшим ключом.
int HeapExtractMax(){
if(heap.size()<1){return 0;}//ERROR
int max = heap[0];
heap[0] = heap[heap.size()-1];
heap.pop_back();
Max_Heapify(0);
return max;
}
УвеличитьКлюч
увеличивает значение ключа элемента x до нового значения k,
которое, как предполагается, не меньше текущего значения ключа x.
void HeapIncreseKey(int index,int key){
if (heap[index]>key){return;}//Error:new key is samller than current
heap[index] = key;
int i = Parent(index);
while(heap[i]<key && i>=0){
heap[index]=heap[i];
heap[i]=key;
index = i;
i = Parent(i);
}
}
ВставитьЭлемент
вставляет элемент x в кучу
void MaxHeapInsert(int key){
heap.push_back(INT32_MIN);
HeapIncreseKey(heap.size()-1,key);
}
полный исходный код класса кучи
#include<iostream>
#include<vector>
using namespace std;
class Heap
{
private:
vector<int> heap;
public:
Heap(vector<int> heap){
this->heap = heap;
}
Heap(int size){
heap.assign(size,0);
}
void printHeap(){
for(int i = 0;i<heap.size();i++){
cout<<heap[i]<<" ";
}
cout<<endl;
}
int leftChild(int index) {return (2*index+1);}
int RightChild(int index) {return (2*index+1)+1;}
int Parent(int index) {return (index-1)/2;}
void setHeap(int value,int index){
heap[index] = value;
}
void Max_Heapify(int index){
int left = leftChild(index);
int right = RightChild(index);
int largest = index;
if(left<heap.size()&&heap[left]>heap[index]) largest = left;
else largest = index;
if(right<heap.size()&&heap[right]>heap[largest]) largest = right;
if(largest != index){
int tmp = heap[index];
heap[index] = heap[largest];
heap[largest] = tmp;
Max_Heapify(largest);
}
}
void BuildMaxHeap(){
for(int i = (heap.size()/2)-1;i>=0;i--){
Max_Heapify(i);
}
}
static vector<int> heapSort(Heap h){
vector<int>sorted;
h.BuildMaxHeap();
for(int i = h.heap.size()-1;i>0;i--){
sorted.push_back(h.heap[0]);
h.heap[0] = h.heap[i];
h.heap.pop_back();
h.printHeap();
h.Max_Heapify(0);
}
return sorted;
}
int MaxElement(){return heap[0];}
int HeapExtractMax(){
if(heap.size()<1){return 0;}//ERROR
int max = heap[0];
heap[0] = heap[heap.size()-1];
heap.pop_back();
Max_Heapify(0);
return max;
}
void HeapIncreseKey(int index,int key){
if (heap[index]>key){return;}//Error:new key is samller than current
heap[index] = key;
int i = Parent(index);
while(heap[i]<key && i>=0){
heap[index]=heap[i];
heap[i]=key;
index = i;
i = Parent(i);
}
}
void MaxHeapInsert(int key){
heap.push_back(INT32_MIN);
HeapIncreseKey(heap.size()-1,key);
}
};
int main(){
vector<int> vec {4,1,3,2,16,9,10,14,8,7};
Heap heap(vec);
heap.BuildMaxHeap();
heap.printHeap();
heap.HeapIncreseKey(4,30);
heap.printHeap();
}
