Минимальная куча в Java

Опубликовано: 4 Февраля, 2022

Min-Heap - это полное двоичное дерево, в котором значение в каждом внутреннем узле меньше или равно значениям в дочерних элементах этого узла.
Отображение элементов кучи в массив тривиально: если узел хранится с индексом k , то его левый дочерний элемент сохраняется с индексом 2k + 1, а его правый дочерний элемент - с индексом 2k + 2 .

Пример минимальной кучи:

            5 13
         /  /   
       10 15 16 31 
      / /  / 
    30 41 51 100 41

Как представлена Min Heap?
Мин-куча - это полное двоичное дерево. Минимальная куча обычно представлена в виде массива. Корневой элемент будет в Arr [0] . Для любого i-го узла, т.е. Arr [i] :

Arr [(i -1) / 2] возвращает свой родительский узел.
Arr [(2 * i) + 1] возвращает левый дочерний узел.
Arr [(2 * i) + 2] возвращает его правый дочерний узел.

Операции с Min Heap:

getMin (): возвращает корневой элемент Min Heap. Время Сложность этой операции - O (1) .
extractMin (): удаляет минимальный элемент из MinHeap. Сложность этой операции по времени составляет O (Log n), поскольку эта операция должна поддерживать свойство кучи (путем вызова heapify ()) после удаления root.
insert (): вставка нового ключа занимает время O (Log n) . Добавляем новый ключ в конец дерева. Если новый ключ больше, чем его родительский, нам не нужно ничего делать. В противном случае нам нужно пройти вверх, чтобы исправить нарушенное свойство кучи.

Ниже представлена реализация Min Heap на Java.

Using Library Functions
We use PriorityQueue class to implement Heaps in Java. By default Min Heap is implemented by this class.

// Java program to demonstrate working of PriorityQueue
import java.util.*;
  
class Example {
  
    // Driver code
    public static void main(String args[])
    {
        // Creating empty priority queue
        PriorityQueue<Integer> pQueue = new PriorityQueue<Integer>();
  
        // Adding items to the pQueue using add()
        pQueue.add(10);
        pQueue.add(30);
        pQueue.add(20);
        pQueue.add(400);
  
        // Printing the most priority element
        System.out.println("Head value using peek function:" + pQueue.peek());
  
        // Printing all elements
        System.out.println("The queue elements:");
        Iterator itr = pQueue.iterator();
        while (itr.hasNext())
            System.out.println(itr.next());
  
        // Removing the top priority element (or head) and
        // printing the modified pQueue using poll()
        pQueue.poll();
        System.out.println("After removing an element "
                           + "with poll function:");
        Iterator<Integer> itr2 = pQueue.iterator();
        while (itr2.hasNext())
            System.out.println(itr2.next());
  
        // Removing 30 using remove()
        pQueue.remove(30);
        System.out.println("after removing 30 with"
                           + " remove function:");
        Iterator<Integer> itr3 = pQueue.iterator();
        while (itr3.hasNext())
            System.out.println(itr3.next());
  
        // Check if an element is present using contains()
        boolean b = pQueue.contains(20);
        System.out.println("Priority queue contains 20 "
                           + "or not?: " + b);
  
        // Getting objects from the queue using toArray()
        // in an array and print the array
        Object[] arr = pQueue.toArray();
        System.out.println("Value in array: ");
        for (int i = 0; i < arr.length; i++)
            System.out.println("Value: " + arr[i].toString());
    }
}

Output:

Head value using peek function:10
The queue elements:
10
30
20
400
After removing an element with poll function:
20
30
400
after removing 30 with remove function:
20
400
Priority queue contains 20 or not?: true
Value in array: 
Value: 20
Value: 400

Вниманию читателя! Не переставай учиться сейчас. Ознакомьтесь со всеми важными концепциями Java Foundation и коллекций с помощью курса "Основы Java и Java Collections" по доступной для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Picked Java

Минимальная куча в Java

РЕКОМЕНДУЕМЫЕ СТАТЬИ