Куча

Термины   11 Март 2012  Автор статьи:  

Кучей (англ. heap) называется массив вида h_0,h_1...h_{n-1}, если в нем выполняется следующее условие:\forall i: \hspace{5}  0<i<n \hspace{5}  h_{\lfloor{\frac{i-1}{2}}\rfloor} \ge h_i, где в скобках \lfloor\rfloor обозначена нижняя целая граница числа. Элемент с индексом \lfloor\frac{i-1}{2}\rfloor будем называть предком элемента с индексом i.

Куча в виде массива

Кучу удобно изображать в виде дерева корнем вверх, где у каждого элемента i, отличного от корня, предком будет являться элемент с индексом \lfloor\frac{i-1}{2}\rfloor.

Куча в виде дерева(в черные цифры -- индекс элемента в массиве, синие -- сам эелемент)

У всех элементов, кроме листьев(самый нижний слой дерева) не более двух сыновей, индексы которых вычисляются по формулам (2i+1),(2i+2). Если номер не попадает в границы массива, то такого сына нет. Очевидно, что куча — это двоичное дерево, у которого значение в любой вершине меньше либо равно значению элемента в предке этой вершины. Самый максимальный элемент находится в вершине кучи(корне дерева), а высота кучи составляет h=O(n log(n)).

Основные операции с кучей

1. Добавление элемента в кучу(англ HeapPush).

Пусть у нас имеется (n-1) элементная куча h[0…n-2]. Необходимо добавить в нее элемент х так, чтобы она продолжала быть кучей.

Алгоритм

  1. Добавить элемент х в конец массива h, сделав его на 1 элемент длиннее.
  2. Обозначим за t номер подвешенного элемента в массиве. Пока значение предка вершины t строго меньше значение вершины t, меняем родителя вершины t и саму вершину t местами, переобозначим t индекс ее предка.

2. Нормализация кучи(англ Heapify).

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

Алгоритм

  1. Сравнить сыновей(или сына) элемента с индексом pos. Если больший из сыновей больше элемента pos, меняем этого сына и pos местами. Переобозначаем за pos индекс наибольшего сына.
  2. Продолжаем шаг 1 пока у элемента с индексом pos есть сыновья или наибольший из сыновей меньше или равен элементу с индексом pos.

3.Построение кучи(англ НеарMake).

Задан массив h длиной n, требуется переставить элементы в нем так, чтобы он стал кучей.

Алгоритм 1

Поэлементно запускаем HeapPush

Такой способ построения работает за O(n log(n)), однако это не самое быстрое время работы алгоритма.

Алгоритм 2

Начиная идти с конца массива, поэлементно применяет Heapify.

В данном случае алгоритм работает быстрее. Очевидно, что на второй половине массива Heapify не сделает вообще перестановок, на второй четверти для каждого элемента будет сделана максимум 1 перестановка в функции Heapyfy, на второй четверти — 2 итд. Если получить сумму перестановок, то полученное число не будет расти быстрее n. То есть, среднее время работы алгоритма будет O(n). Похожий метод построения кучи используется во многих стандартных библиотеках.




Научиться программировать

  • на Delphi

  • на Java

  • на C++