Двоичная куча на Java

Двоичная куча на Java

 

Двоичная куча, пирамида, или сортирующее дерево — такое двоичное дерево, для которого выполняються три условия:

  1. Значение в любой вершине не меньше, чем значения её потомков
  2. Глубина всех листьев (расстояние до корня) отличается не более чем на 1 слой.
  3. Последний слой заполняется слева направо без «дырок».
Подробное описание алгоритма на Википедии

Перейдем к реализации алгоритма двоичной кучи на Java


import java.util.*;
// https://en.wikipedia.org/wiki/Binary_heap
// invariant: heap[parent] <= heap[child]
public class BinaryHeap {
    int[] heap;
    int size;
    public BinaryHeap(int n) {
        heap = new int[n];
    }
    // build heap in O(n)
    public BinaryHeap(int[] values) {
        heap = values.clone();
        size = values.length;
        for (int pos = size / 2 - 1; pos >= 0; pos--)
            down(pos);
    }
    public int removeMin() {
        int removed = heap[0];
        heap[0] = heap[--size];
        down(0);
        return removed;
    }
    public void add(int value) {
        heap[size] = value;
        up(size++);
    }
    void up(int pos) {
        while (pos > 0) {
            int parent = (pos - 1) / 2;
            if (heap[pos] >= heap[parent])
                break;
            swap(pos, parent);
            pos = parent;
        }
    }
    void down(int pos) {
        while (true) {
            int child = 2 * pos + 1;
            if (child >= size)
                break;
            if (child + 1 < size && heap[child + 1] < heap[child])
                ++child;
            if (heap[pos] <= heap[child])
                break;
            swap(pos, child);
            pos = child;
        }
    }
    void swap(int i, int j) {
        int t = heap[i];
        heap[i] = heap[j];
        heap[j] = t;
    }
    // random test
    public static void main(String[] args) {
        Random rnd = new Random(1);
        for (int step = 0; step < 1000; step++) {
            int n = rnd.nextInt(100) + 1;
            PriorityQueue<Integer> q = new PriorityQueue<>();
            BinaryHeap h = new BinaryHeap(n);
            for (int op = 0; op < 1000; op++) {
                if (rnd.nextBoolean() && q.size() < n) {
                    int v = rnd.nextInt();
                    q.add(v);
                    h.add(v);
                } else if (!q.isEmpty()) {
                    if (q.remove() != h.removeMin())
                        throw new RuntimeException();
                }
            }
        }
    }
}

566