Эта серия представляет собой краткое изложение структур данных и алгоритмов, когда я искал работу много лет назад. Здесь есть базовые части и классические вопросы для интервью от крупных компаний. Впервые опубликовано на CSDN. Теперь он организован в серию для справки друзей, которым это нужно.Если есть какая-либо ошибка, пожалуйста, поправьте меня. Полный кодовый адрес этой серии находится по адресуздесь.
0 Обзор
Куча, описываемая в этой статье, является двоичной кучей. Двоичная куча — это объект массива, который можно рассматривать как полное бинарное дерево.Каждый узел в дереве соответствует элементу в массиве, в котором хранится значение узла. Каждый уровень дерева заполнен, кроме последнего уровня. Двоичная куча может использоваться для реализации сортировки кучи, приоритетной очереди и т. д. Кодовый адрес этой статьи находится по адресуздесь.
1 Определение двоичной кучи
Используйте массивы для реализации двоичных куч, двоичные кучи имеют два свойства, гдеLENGTH(A)представляет массивAдлина иHEAP_SIZE(A)представляет количество элементов кучи, хранящихся в A, гдеLENGTH(A) <= HEAP_SIZE(A), то есть хотяA[0,1,...N-1]может содержать допустимые значения, ноA[HEAP_SIZE(A)-1]Элементы после этого не принадлежат соответствующей куче.
Корень дерева, соответствующий двоичной куче, равенA[0], учитывая индекс i узла, можно легко вычислить его родительский узел и дочерний узел.Обратите внимание, что в следующих примерах диаграмм мы помечаем элементы так, чтобы они начинали отсчет с 1, а код реализации начинал отсчет с 0.
#define PARENT(i) ( i > 0 ? (i-1)/2 : 0)
#define LEFT(i) (2 * i + 1)
#define RIGHT(i) (2 * i + 2)
Примечание. Каждый слой дерева, соответствующий куче, заполнен, поэтому высотаhКоличество элементов в куче не более1+2+2^2+...2^h = 2^(h+1) - 1(полное бинарное дерево), минимальное количество элементов равно1+2+...+2^(h-1) + 1 = 2^h.
из-за количества элементов2^h <= n <= 2^(h+1) -1,такh <= lgn < h+1,следовательноh = lgn. То есть высота двоичной кучи, содержащей n элементов, равнаlgn.
2 Сохраняйте свойства кучи
В этой статье в основном создается максимальная куча, и принцип минимальной кучи аналогичен. Чтобы сохранить свойства кучи,maxHeapify(int A[], int i)функция создания массива кучиAотбросить максимальную кучу так, чтобыiКорневое поддерево становится максимальной кучей.
void maxHeapify(int A[], int i, int heapSize)
{
int l = LEFT(i);
int r = RIGHT(i);
int largest = i;
if (l <= heapSize-1 && A[l] > A[i]) {
largest = l;
}
if (r <= heapSize-1 && A[r] > A[largest]) {
largest = r;
}
if (largest != i) { // 最大值不是i，则需要交换i和largest的元素，并递归调用maxHeapify。
swapInt(A, i, largest);
maxHeapify(A, largest, heapSize);
}
}
-
На каждом шаге алгоритма из элемента
A[i]а такжеA[left]так же какA[right]Выберите среди них наибольший и сохраните его в нижнем индексеlargestсередина. еслиA[i]максимум, тоiКорневое поддерево уже является максимальной кучей, и программа завершается. -
в противном случае,
iДочерний узел имеет самый большой элемент,A[i]а такжеA[largest]swap, чтобы i и его дочерние элементы удовлетворяли свойству max-heap. Кроме того, индексlargestЗначение узла после свопа становитсяA[i], поддерево с корнем в этом узле может нарушать свойство максимальной кучи, поэтому необходимо рекурсивно вызывать поддеревоmaxHeapify()функция.
когдаmaxHeapify()функция работает наiявляется корневым узлом, размерnКогда на поддереве , время выполнения корректируется дляA[i],A[left],A[right]времяO(1), плюс кiрекурсивно вызывать поддерево с корнем в дочернем узлеmaxHeapifyвремя.iРазмер поддерева, узлом которого является корень, не более2n/3(когда нижний слой заполнен только наполовину), поэтому его можно толкнутьT(N) <= T(2N/3) + O(1),такT(N)=O(lgN).
На следующем рисунке показан бегmaxHeapify(heap, 2)пример.A[] = {16, 4, 10, 14, 7, 9, 3, 2, 8, 1}, размер кучи10.
3 Создайте максимальную кучу
Мы можем знать, что массивA[0, 1, ..., N-1]середина,A[N/2, ..., N-1]Элементами являются все листовые узлы дерева. как на фото выше6-10Все узлы являются листовыми узлами. Каждый листовой узел можно рассматривать как максимальную кучу только с одним элементом, поэтому нам нужно вызывать только другие узлы.maxHeapify()функция.
void buildMaxHeap(int A[], int n)
{
int i;
for (i = n/2-1; i >= 0; i--) {
maxHeapify(A, i, n);
}
}
Причина, по которой эта функция верна, нам нужно доказать, мы можем использовать инварианты цикла, чтобы доказать это.
Инвариант цикла: перед запуском цикла for узелi+1、i+2...N-1являются корнями максимальной кучи.
Инициализация: прежде чем цикл for начнет повторяться,i = N/2-1, УзелN/2, N/2+1, ..., N-1Они оба являются листовыми узлами и корнем максимальной кучи.
держать: потому что узелiМетки дочерних узлов больше, чемiБольшие, согласно определению инварианта цикла, эти дочерние узлы являются корнем максимальной кучи, поэтому вызовитеmaxHeapify()назад,iстановится корнем максимальной кучи, иi+1, i+2, ..., N-1По-прежнему сохраняйте максимальные свойства кучи.
Завершение: когда процесс завершается, i=0, поэтому узел0, 1, 2, ..., N-1Оба являются корнем максимальной кучи, в частности, узел 0 является корнем максимальной кучи.
Хотя каждый звонокmaxHeapify()время - этоO(lgN), в целомO(N)звонки, но говорят, что время выполненияO(NlgN)является неточным, если быть точным, время работы равноO(N), это не будет доказано здесь. Для конкретного процесса доказательства, пожалуйста, обратитесь к «Введение в алгоритмы».
4 куча сортировки
начатьbuildMaxHeap()Функция создает максимальную кучу, потому что самый большой элемент массива находится вA[0], непосредственно комбинируя его сA[N-1]Поменяйте местами, чтобы достичь конечной правильной позиции. УдалитьA[N-1], размер кучиheapSizeВычесть 1, позвонитьmaxHeapify(heap, 0, --heapSize)Сохраняйте свойство max-heap, пока размер кучи не уменьшится с N до 1.
void heapSort(int A[], int n)
{
buildMaxHeap(A, n);
int heapSize = n;
int i;
for (i = n-1; i >= 1; i--) {
swapInt(A, 0, i);
maxHeapify(A, 0, --heapSize);
}
}
5 Приоритетная очередь
Наконец, реализована очередь с максимальным приоритетом.Есть четыре основные операции, а именно:
-
insert(PQ， key): Вставить ключ в очередь. -
maximum(PQ): возвращает элемент с самым большим ключом в очереди. -
extractMax(PQ): удалить и вернуть элемент с самым большим ключом в очереди -
increaseKey(PQ, i, key): увеличить значение ключа в очереди i до ключа
определить структуру здесьPriorityQueueПростота в эксплуатации.
typedef struct PriorityQueue {
int capacity;
int size;
int elems[];
} PQ;
Код реализации операции конечной приоритетной очереди выглядит следующим образом:
/**
* 从数组创建优先级队列
*/
PQ *newPQ(int A[], int n)
{
PQ *pq = (PQ *)malloc(sizeof(PQ) + sizeof(int) * n);
pq->size = 0;
pq->capacity = n;
int i;
for (i = 0; i < pq->capacity; i++) {
pq->elems[i] = A[i];
pq->size++;
}
buildMaxHeap(pq->elems, pq->size);
return pq;
}
int maximum(PQ *pq)
{
return pq->elems[0];
}
int extractMax(PQ *pq)
{
int max = pq->elems[0];
pq->elems[0] = pq->elems[--pq->size];
maxHeapify(pq->elems, 0, pq->size);
return max;
}
PQ *insert(PQ *pq, int key)
{
int newSize = ++pq->size;
if (newSize > pq->capacity) {
pq->capacity = newSize * 2;
pq = (PQ *)realloc(pq, sizeof(PQ) + sizeof(int) * pq->capacity);
}
pq->elems[newSize-1] = INT_MIN;
increaseKey(pq, newSize-1, key);
return pq;
}
void increaseKey(PQ *pq, int i, int key)
{
int *elems = pq->elems;
elems[i] = key;
while (i > 0 && elems[PARENT(i)] < elems[i]) {
swapInt(elems, PARENT(i), i);
i = PARENT(i);
}
}
использованная литература
- Введение в алгоритмы Глава 6 Сортировка кучей