Структуры данных: пирамида (двоичная куча) в Java

Пирамида (она же куча, двоичная куча, binary heap) это полное двоичное дерево, в котором значение каждого узла не меньше значений его потомков, а хранится оно обычно в обычном массиве. Вставка и удаление занимают O(logN), а максимум всегда лежит в корне, то есть в нулевом элементе массива. Именно на такой структуре в Java построен класс java.util.PriorityQueue, и ее же используют планировщики задач и алгоритмы вроде пирамидальной сортировки. Ниже разбор всех операций на схемах и полная реализация на Java.

Кратко

• Пирамида это полное двоичное дерево: все уровни заполнены, кроме последнего, а он заполняется слева направо. Благодаря полноте дерево укладывается в массив без пропусков.
• Главное правило (свойство кучи): значение любого узла больше или равно значениям его потомков. Максимум всегда в корне, но соседние ветки между собой не упорядочены.
• Индексы в массиве считаются арифметикой: потомки узла i лежат в 2i+1 и 2i+2, родитель узла i в (i-1)/2. Ни ссылок, ни указателей не нужно.
• Вставка: новый элемент кладут в конец и поднимают вверх, меняя местами с родителем, пока родитель меньше. Это displaceUp.
• Удаление: на место удаленного ставят последний элемент и опускают его вниз, меняя местами с большим из потомков. Это displaceDown. Замена значения использует то же самое, только направление выбирается по сравнению со старым значением.
• Все операции стоят O(logN), потому что высота полного дерева из N узлов равна log2(N).

Никто не будет отрицать, что алгоритмы и структуры данных это неоспоримый фундамент программирования. Да, можно и работать программистом и без их знания, но увы, далеко вы так не уедете. Поэтому чтобы усилить вашу базу знаний в этой области, хотелось бы поговорить о такой структуре данных как пирамида (еще известная как куча и двоичная куча). Как правило такие структуры данных применяют в различных планировщиках и других структурах, в которых нужно обозначить приоритетность различных задач. Итак...Пирамида это разновидность дерева, которая обеспечивает вставку/удаление за время O(logN) и обладает следующими свойствами:

• Полнота. Все уровни дерева содержат все возможные узлы, кроме последнего, который может быть заполнен лишь частично и который заполняется слева-направо;
• Пирамида как правило реализуется на базе массива;
• Для каждого узла в пирамиде есть основополагающее условие, что значение каждого узла больше (или равно) значениям его потомков. Соответственно, максимум будет храниться в верхнем элементе.

Пирамида, состоящая из вершин, которые хранят значения не выше 10:Хотелось бы отметить, что по сравнению с деревом двоичного поиска пирамида является слабо упорядоченной, так как в дереве двоичного поиска ключ левого потомка меньше ключа правого потомка, а в пирамиде такое условие отсутствует.

Пирамида и двоичное дерево поиска: сравнение

Чтобы разница была нагляднее, вот два дерева рядом:

Удаление элемента по индексу

Для начала давайте рассмотрим, какова же последовательность действий при удалении выбранного узла:

1. Удалить выбранный узел.
2. Переместить последний узел, в последнем ряду на место удаленного.
3. Смещать его вниз до тех пор, пока он не окажется ниже большего и выше меньшего узла.

Когда используют пирамиду, то как правило необходимо уметь удалять вершину (нулевой элемент внутреннего массива) или последний (тогда операции по перемещению можно опустить, оставив только удаление элемента). В качестве примера удаления элемента по индексу в рассматриваемой нами пирамиде выше мы удалим узел со значением 7:

1. Удаляем выбранный узел и помещаем на его место последний, который у нас имеет значение 4:

   Но в таком положении данный узел не соответствует условию, что каждый узел потомок не должен быть больше рассматриваемого, не так ли?

   Поэтому:

2. Меняем его местами с наибольшим из потомков, который имеет значение 6:

   Далее смотрим, нет ли потомков со значением большим, чем у нашего смещаемого элемента, и видим что нет, а это значит, что элемент стал на свое место.

Вставка нового элемента

Каковы же действия при вставке нового элемента:

1. Вставляемый узел помещается в конец пирамиды.

   Но ведь у нас же есть условие, что дочерний элемент не может иметь значение больше родительского, верно?

   Поэтому:

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

К примеру, в пирамиду, которая была получена в результате удаления элемента, мы хотим добавить элемент со значением 8:

1. Помещаем новый узел в конец пирамиды:

2. Сравниваем новый элемент с родительским элементом, который имеет значение 4.

   Так как новый элемент больше родительского, меняем их местами:

3. Сравниваем новый элемент с новым его родителем и видим, что наш элемент больше и его (8>6), поэтому меняем местами и их:

   Опять же, сравниваем элемент с родительский элементом и видим, что в этот раз родительский элемент больше, а это значит что наш новый элемент стал на свое место.

Замена элемента

При замене элемента сперва нужно заменить элемент с заданным индексом. Логично, не так ли? Ну а что далее? Ведь новое значение элемента уже другое, и не факт, что оно соответствует условию пирамиды. То есть не факт что все дочерние элементы меньше вставляемого элемента. Также не факт, что родительские элементы больше нового. Поэтому сперва нужно сравнить со старым значением элемента:

• если новый элемент больше, чем он, то нам нужно сравнивать его с родительскими элементами и при надобности менять их местами;
• если же новый элемент меньше, то нужно сравнивать с большим из дочерних элементов и менять местами, если дочерний элемент окажется больше (до тех пор, пока новый элемент не станет на допустимое место).

Давайте же это рассмотрим на нашем примере. Сейчас мы хотим вставить элемент со значением 1 вместо элемента со значением 9:

1. Вставляем элемент на место предыдущего:
2. Сравниваем предыдущий элемент 9 и новый 1 и видим, что меньше, а значит, мы будем пробовать смещать вниз.
3. Сравниваем с большим элементом из дочерних, то есть с тем, который имеет значение 5, и видим, что новый меньше. Поэтому меняем сравниваемые элементы местами:
4. Так как сейчас новых элементов ниже нашего нового уже нет, можно сказать, что элемент встал на свое место.

Реализация пирамиды на Java

После понимания принципа работы данной структуры самое время рассмотреть реализацию пирамиды на Java: Класс, представляющий одну вершину и значение, которое она содержит:

public class Node {
  private int value;

  public Node(int value) {
     this.value = value;
  }

  public int getValue() {
     return this.value;
  }

  public void setValue(int value) {
     this.value = value;
  }
}

Здесь вершина хранит только int, поэтому и пирамида получится только для чисел. Чтобы класть в нее произвольные объекты, вершину делают обобщенной (Node<T extends Comparable<T>>) или передают в пирамиду компаратор и сравнивают элементы через него. Класс, представляющий саму пирамиду:

public class Heap {
  private Node[] heapArray; // массив со всеми вершинами
  private int maxSize; // размер массива
  private int currentSize; // количество узлов в массиве

  public Heap(int maxSize) { // создание пустой пирамиды
     this.maxSize = maxSize;
     this.currentSize = 0;
     heapArray = new Node[maxSize];
  }

  public void printHeap() { // отображение пирамиды в консоль
     System.out.println("Массив значений: ");

     for (int n = 0; n < currentSize; n++) {
        if (heapArray[n] != null) {
           System.out.print(heapArray[n].getValue() + " ");
        }
        else {
           System.out.print("- ");
        }
     }
     System.out.println();

     int countOfGaps = 32;
     int itemsPerRow = 1;
     int columnNumber = 0; // номер элемента в данной строке
     String lines = "___________________________________________________________________";
     System.out.println(lines);
     for (int i = 0; i < currentSize; i++) {
        if (columnNumber == 0) {  // проверяем первый элемент ли в текущей строке
           for (int k = 0; k < countOfGaps; k++) { // добавляем предшествующие пробелы
              System.out.print(' ');
           }
        }
        System.out.print(heapArray[i].getValue());// выводим в консоль значение вершины

        if (++columnNumber == itemsPerRow) { // проверяем последний ли элемент в строке
           countOfGaps /= 2; // уменьшаем количество отступов, применяемое для следующей строки
           itemsPerRow *= 2; // указываем, что элементов может быть вдвое больше
           columnNumber = 0; // сбрасываем счетчик для текущего элемента строки
           System.out.println(); // переходим на новую строку
        }
        else { //переход к следующему элементу
           for (int k = 0; k < countOfGaps * 2 - 2; k++) {
              System.out.print(' '); // добавляем отступы
           }
        }
     }
     System.out.println("\n" + lines); // нижний пунктир
  }

  public boolean insertNode(int value) { // вставка нового значения
     if (currentSize == maxSize) { // проверяем не выходим ли мы за рамки массива
        return false;
     }
     Node newNode = new Node(value);// создание вершины с данным значением
     heapArray[currentSize] = newNode;// вершину задаем в самый низ дерева
     displaceUp(currentSize++);// пытаемся поднять вершину, если значение вершины позволяет
     return true;
  }

  public Node removeNode(int index) { // удалить элемент по индексу массива
     if(index >= 0 && currentSize > index) {
        Node root = heapArray[index];
        heapArray[index] = heapArray[--currentSize]; // задаем элементу с переданным индексом значение последнего элемента
        heapArray[currentSize] = null;// последний элемент удаляем
        displaceDown(index);// проталкиваем вниз новый элемент, чтобы он занял должное ему место
        return root;
     }
     return null;
  }

  public boolean changeNode(int index, int newValue) {
     if (index < 0 || currentSize<=index) {
        return false;
     }
     int oldValue = heapArray[index].getValue(); // сохраняем старое значение
     heapArray[index].setValue(newValue); // присваиваем новое

     if (oldValue < newValue) {// если узел повышается
        displaceUp(index);     // выполняется смещение вверх
     }
     else {                  // если понижается
        displaceDown(index);   // смещение вниз
     }
     return true;
  }

  private void displaceUp(int index) { //смещение вверх
     int parentIndex = (index - 1) / 2; // узнаем индекс родителя
     Node bottom = heapArray[index]; // берем элемент
     while (index > 0 && heapArray[parentIndex].getValue() < bottom.getValue()) {// если родительский элемент меньше
        heapArray[index] = heapArray[parentIndex];// то меняем его местами с рассматриваемым
        index = parentIndex;
        parentIndex = (parentIndex - 1) / 2;// берем новый родительский индекс и повторяем сравнение элементов
     }
     heapArray[index] = bottom;// сохраняем результат
  }

  private void displaceDown(int index) {// смещение вниз
     int largerChild;
     Node top = heapArray[index]; // сохранение корня, пока у узла есть хотя бы один потомок
     while (index < currentSize / 2) {// если данное условие не выполняется то элемент уже в самом низу пирамиды
        int leftChild = 2 * index + 1; // вычисляем индексы в массиве для левого узла ребенка
        int rightChild = leftChild + 1;// и правого

        if (rightChild < currentSize && heapArray[leftChild].getValue() < heapArray[rightChild].getValue()) {
           largerChild = rightChild;
        }// вычисляем ребенка вершину с наибольшим числовым значением
        else {
           largerChild = leftChild;
        }

        if (top.getValue() >= heapArray[largerChild].getValue()) {// если значение вершины больше или равно
           //значения его наибольшего ребенка
           break;// то выходим из метода
        }

        heapArray[index] = heapArray[largerChild];// заменяем вершину, большей дочерней вершиной
        index = largerChild; // текущий индекс переходит вниз
     }
     heapArray[index] = top; // задаем конечное местоположение для элемента
  }
}

И наконец, давайте посмотрим на нашу пирамиду в деле:

public class Solution {

  public static void main(String[] args) {
     // задаем начальные данные:
     Heap heap = new Heap(31);
     heap.insertNode(120);
     heap.insertNode(40);
     heap.insertNode(50);
     heap.insertNode(80);
     heap.insertNode(20);
     heap.insertNode(100);
     heap.insertNode(150);
     heap.insertNode(30);
     heap.insertNode(210);
     heap.insertNode(180);
     heap.insertNode(10);
     heap.insertNode(90);
      // выводим начальную пирамиду в консоль
     heap.printHeap();

Вывод в консоли:

// изменяем элемент под индексом 0 с 210 на 15, и выводим в консоль измененную пирамиду
     heap.changeNode(0,15);
     heap.printHeap();

Вывод в консоли:

// удаляем элемент под индексом 3, который имеет значение 80 и смотрим на изменившуюся пирамиду
     heap.removeNode(3);
     heap.printHeap();
  }
}

Вывод в консоли: Ну вот, собственно, и все по собственной реализации. Стоит добавить, что в стандартной библиотеке такая структура уже есть: это java.util.PriorityQueue из Java 5, в документации он так и описан, как очередь на основе кучи. По умолчанию это min-heap, то есть в голове очереди лежит наименьший элемент, а чтобы получить привычную нам пирамиду с максимумом наверху, в конструктор передают компаратор:

PriorityQueue<Integer> heap = new PriorityQueue<>(Comparator.reverseOrder());
heap.offer(120);
heap.offer(210);
heap.offer(40);

System.out.println(heap.peek()); // 210, максимум лежит в голове очереди
System.out.println(heap.poll()); // 210, элемент извлечен из кучи
System.out.println(heap.peek()); // 120, наверх поднялся следующий по величине

Методы offer() и poll() стоят те же O(logN), а peek() работает за константу. Свою реализацию пишут ради понимания устройства или ради операций, которых у PriorityQueue нет: например, изменить значение по индексу, как в методе changeNode выше. Ну вот, собственно, и все. Всем спасибо за внимание!

Вопросы и ответы

Что такое двоичная куча (пирамида) простыми словами?

Это полное двоичное дерево, в котором каждый узел не меньше своих потомков, а само дерево лежит в массиве. Из-за такого правила максимум всегда оказывается в корне, и его можно взять мгновенно, а вставка нового элемента или удаление корня обходятся в O(logN). Именно поэтому кучу берут там, где нужно постоянно доставать самый приоритетный элемент: планировщики задач, очереди сообщений, алгоритм Дейкстры.

Чем куча отличается от двоичного дерева поиска?

Упорядоченностью и формой. В дереве поиска порядок строгий: слева от узла меньшие значения, справа большие, поэтому искать произвольный элемент можно за O(logN). В куче порядок слабый: узел больше своих потомков, но левая и правая ветки между собой никак не связаны, и поиск произвольного значения превращается в перебор за O(N). Зато куча всегда остается полным деревом, поэтому ее хранят в массиве и она не вырождается в список. Подробнее про деревья поиска в отдельной статье о двоичном дереве.

Как найти родителя и потомков узла в массиве?

Арифметикой по индексу: для узла с индексом i левый потомок лежит в 2i+1, правый в 2i+2, а родитель в (i-1)/2 при целочисленном делении. Проверять существование потомка нужно по текущему размеру: если 2i+1 больше или равен количеству элементов, потомков у узла нет. Именно эти формулы и использованы в методах displaceUp и displaceDown из примера.

Почему операции с кучей стоят O(logN)?

Потому что элемент при вставке или удалении проходит путь от корня до листа или обратно, а высота полного двоичного дерева из N узлов равна log2(N): на каждом уровне число узлов удваивается. Для миллиона элементов это всего 20 шагов. Просмотр всех элементов (например, вывод в консоль) остается линейным, O(N).

Есть ли готовая куча в стандартной библиотеке Java?

Да, это java.util.PriorityQueue из Java 5: в документации он прямо описан как очередь на основе кучи, где offer() и poll() работают за O(log(n)), а peek() за константу. По умолчанию это min-heap, то есть в голове очереди лежит наименьший элемент; чтобы получить max-heap, в конструктор передают компаратор, например new PriorityQueue<>(Comparator.reverseOrder()). Свою реализацию пишут ради понимания или ради специфических операций вроде изменения значения по индексу.

Что такое пирамидальная сортировка и при чем тут куча?

Это сортировка (heapsort), которая строит из массива кучу, а затем N раз забирает максимум из корня и меняет его местами с последним элементом, уменьшая рабочую часть массива. Каждое извлечение стоит O(logN), всего получается O(N logN) в любом случае, без худших сценариев, и сортировка работает на месте, не требуя дополнительной памяти. В самой JDK Arrays.sort() использует другие алгоритмы, но идея кучи применяется в PriorityQueue. Читайте также:

• Коллекции в Java: Java Collections Framework
• TreeSet в Java
• Рекурсия в Java