Что такое структура данных Heap?

Структура данных Heap

Heap (куча) — это специализированная древовидная структура данных, которая удовлетворяет свойству кучи: каждый родитель имеет значение больше (для max-heap) или меньше (для min-heap) своих дочерних элементов. Heap часто используется для реализации приоритетной очереди и алгоритма сортировки heapsort.

Важное уточнение терминологии

Важно не путать два разных понятия:

• Heap (структура данных) — приоритетная очередь на основе дерева
• Heap (память в Java) — область памяти, где создаются объекты (другой контекст)

Мы говорим о первом — структуре данных.

Основные свойства

1. Свойство кучи (Heap Property)

Для max-heap: Parent ≥ Left child AND Parent ≥ Right child Для min-heap: Parent ≤ Left child AND Parent ≤ Right child

2. Полное бинарное дерево (Complete Binary Tree)

Все уровни заполнены полностью, кроме, возможно, последнего.

    10          <- Root (максимум в max-heap)
   /  \
  9    8
 / \  / \
7  6 5  4      <- Все внутренние элементы меньше родителей
/
3

Типы Heap

1. Max Heap (максимальная куча)

Родитель всегда больше своих детей:

       100
       / \
      50  30
     / \  / \
    40 10 20 15

2. Min Heap (минимальная куча)

Родитель всегда меньше своих детей:

       10
       / \
      20  30
     / \  / \
    40 50 35 40

Реализация на Java

1. Использование PriorityQueue (готовое решение)

import java.util.PriorityQueue;
import java.util.Comparator;

public class HeapExample {
    public static void main(String[] args) {
        // Min heap (по умолчанию)
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        minHeap.add(50);
        minHeap.add(30);
        minHeap.add(70);
        minHeap.add(10);
        
        System.out.println(minHeap.poll());  // 10
        System.out.println(minHeap.poll());  // 30
        System.out.println(minHeap.poll());  // 50
        System.out.println(minHeap.poll());  // 70
        
        // Max heap (обратный компаратор)
        PriorityQueue<Integer> maxHeap = 
            new PriorityQueue<>(Comparator.reverseOrder());
        maxHeap.add(50);
        maxHeap.add(30);
        maxHeap.add(70);
        maxHeap.add(10);
        
        System.out.println(maxHeap.poll());  // 70
        System.out.println(maxHeap.poll());  // 50
        System.out.println(maxHeap.poll());  // 30
        System.out.println(maxHeap.poll());  // 10
    }
}

2. Пользовательский класс с Heap

public class MaxHeap {
    private int[] heap;
    private int size;
    
    public MaxHeap(int capacity) {
        heap = new int[capacity];
        size = 0;
    }
    
    // Добавить элемент
    public void add(int value) {
        if (size == heap.length) {
            throw new IllegalStateException("Heap переполнена");
        }
        
        heap[size] = value;
        heapifyUp(size);  // Восстанавливаем свойство кучи
        size++;
    }
    
    // Получить максимум (не удаляя)
    public int peek() {
        if (size == 0) {
            throw new IllegalStateException("Heap пуста");
        }
        return heap[0];  // Корень всегда максимален в max-heap
    }
    
    // Удалить и получить максимум
    public int poll() {
        if (size == 0) {
            throw new IllegalStateException("Heap пуста");
        }
        
        int max = heap[0];
        heap[0] = heap[size - 1];  // Переместить последний элемент на место корня
        size--;
        heapifyDown(0);  // Восстанавливаем свойство кучи
        return max;
    }
    
    // Восстановление кучи снизу вверх (при добавлении)
    private void heapifyUp(int index) {
        while (index > 0) {
            int parentIndex = (index - 1) / 2;
            if (heap[parentIndex] >= heap[index]) {
                break;  // Свойство восстановлено
            }
            swap(index, parentIndex);
            index = parentIndex;
        }
    }
    
    // Восстановление кучи сверху вниз (при удалении)
    private void heapifyDown(int index) {
        while (true) {
            int largestIndex = index;
            int leftChild = 2 * index + 1;
            int rightChild = 2 * index + 2;
            
            if (leftChild < size && heap[leftChild] > heap[largestIndex]) {
                largestIndex = leftChild;
            }
            if (rightChild < size && heap[rightChild] > heap[largestIndex]) {
                largestIndex = rightChild;
            }
            
            if (largestIndex == index) {
                break;  // Свойство восстановлено
            }
            
            swap(index, largestIndex);
            index = largestIndex;
        }
    }
    
    private void swap(int i, int j) {
        int temp = heap[i];
        heap[i] = heap[j];
        heap[j] = temp;
    }
    
    public int getSize() {
        return size;
    }
}

Операции и их сложность

Практические применения

1. Приоритетная очередь

PriorityQueue<Task> taskQueue = new PriorityQueue<>(
    Comparator.comparingInt(Task::getPriority)
);

taskQueue.add(new Task("Критичная", 1));
taskQueue.add(new Task("Низкий приоритет", 10));
taskQueue.add(new Task("Высокий приоритет", 5));

while (!taskQueue.isEmpty()) {
    Task task = taskQueue.poll();
    executeTask(task);  // Выполнять в порядке приоритета
}

2. Алгоритм сортировки (Heapsort)

public class HeapSort {
    public static void heapSort(int[] arr) {
        int n = arr.length;
        
        // Построить heap
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(arr, n, i);
        }
        
        // Извлечь элементы из heap
        for (int i = n - 1; i > 0; i--) {
            // Переместить корень (максимум) в конец
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            
            heapify(arr, i, 0);
        }
    }
    
    private static void heapify(int[] arr, int n, int i) {
        int largest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        
        if (left < n && arr[left] > arr[largest]) {
            largest = left;
        }
        if (right < n && arr[right] > arr[largest]) {
            largest = right;
        }
        
        if (largest != i) {
            int temp = arr[i];
            arr[i] = arr[largest];
            arr[largest] = temp;
            heapify(arr, n, largest);
        }
    }
}

3. Поиск K наименьших элементов

public class KSmallest {
    public static List<Integer> findKSmallest(int[] arr, int k) {
        // Max heap для хранения k наименьших
        PriorityQueue<Integer> maxHeap = 
            new PriorityQueue<>(Comparator.reverseOrder());
        
        for (int num : arr) {
            if (maxHeap.size() < k) {
                maxHeap.add(num);
            } else if (num < maxHeap.peek()) {
                maxHeap.poll();
                maxHeap.add(num);
            }
        }
        
        return new ArrayList<>(maxHeap);
    }
}

Преимущества и недостатки

Преимущества:

• Быстро найти минимум/максимум (O(1))
• Эффективная вставка и удаление (O(log n))
• Используется мало памяти (в одном массиве)
• Хороша для частых операций извлечения экстремумов

Недостатки:

• Поиск произвольного элемента (O(n))
• Не отсортирована полностью
• Сложнее в реализации, чем Array

Heap — это мощная структура данных для решения задач, связанных с приоритетами и экстремумами.