Понять, как реализовать двоичную кучу в Java

Эта статья даст вам полный обзор работы сортировки кучи, а позже мы научимся реализовывать двоичную кучу в Java.

Вот повестка дня для этой статьи:

1. Что такое сортировка в куче?
2. Макс. Куча
3. Мин. Куча
4. Реализация кучи в Java
   • Диаграмма
   • Код

Давайте начнем!

Что такое сортировка в куче?

Куча - это в основном древовидная структура данных. У него есть узлы. Узел состоит из определенных элементов. Каждый узел содержит один элемент.

Узлы могут иметь детей. Если детей нет, он называется Листом.

Следует соблюдать два правила:

• Значение каждого узла должно быть меньше или равно всем значениям, хранящимся в его дочерних элементах.
• У него минимально возможная высота.

Кучи чрезвычайно эффективны при извлечениинаименьший или наибольший элемент.

Теперь перейдем к минимальной куче!

Мин. Куча

Минимальная куча - это полное двоичное дерево, в котором значение корневого элемента меньше или равно любому из дочерних элементов.

Представление минимальной кучи

преобразовать двойное число в целое число Java

Arr [(i-1) / 2]: это вернет родительский узел.

Arr [(2 * i) + 1]: это вернет левый дочерний узел.

Arr [(2 * i) + 2]: это вернет правый дочерний узел.

Существуют определенные методы Min Heap:

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

Теперь перейдем к Max Heap.

Макс куча

Максимальная куча - это полное двоичное дерево, в котором значение корневого элемента больше или равно любому из дочерних элементов.

Max heap тоже состоит из нескольких методов!

• Вставить (): он вставит элемент в кучу.
• Удалить() : он удалит элемент из кучи.
• FindMax (): он найдет максимальный элемент из кучи.
• printHeap (): Он напечатает содержимое кучи

Теперь позвольте мне показать вам реализацию кучи через диаграмму, а затем Javaкод.

Реализация кучи в Java

Диаграмма:

На диаграмме выше показана двоичная куча в Java. Как вы узнали, есть две кучи: минимальная куча и максимальная куча, вот диаграмма:

Теперь, переходя к следующему сегменту, мы увидим, как реализовать двоичную кучу в Java.

Код:

public class BinaryHeap {private static final int d = 2 private int [] heap private int heapSize / ** * Это инициализирует нашу кучу размером по умолчанию. * / public BinaryHeap (int capacity) {heapSize = 0 heap = new int [capacity + 1] Arrays.fill (heap, -1)} / ** * Это проверяет, пуста ли куча или нет * Сложность: O ( 1) * / public boolean isEmpty () {return heapSize == 0} / ** * Это проверяет, заполнена ли куча * Сложность: O (1) * / public boolean isFull () {return heapSize == heap .length} private int parent (int i) {return (i-1) / d} private int kthChild (int i, int k) {return d * i + k} / ** * Это вставит новый элемент в кучу * Сложность: O (log N) * В худшем случае нам нужно пройти до корня * / public void insert (int x) {if (isFull ()) throw new NoSuchElementException ('Куча заполнена, нет места для вставки новый элемент ') heap [heapSize ++] = x heapifyUp (heapSize-1)} / ** * Это удалит элемент с индексом x * Сложность: O (log N) * * / public int delete (int x) {if (isEmpty ()) throw new NoSuchElementException ('Куча пуста, нет элемента для удаления') int key = heap [x] heap [x] = heap [heapSize -1] heapSize - heapifyDown (x) retu rn key} / ** * Этот метод используется для сохранения свойства кучи при вставке элемента. * * / private void heapifyUp (int i) {int temp = heap [i] while (i> 0 && temp> heap [parent (i)]) {heap [i] = heap [parent (i)] i = parent (i)} heap [i] = temp} / ** * Этот метод используется для сохранения свойства кучи при удалении элемента. * * / private void heapifyDown (int i) {int child int temp = heap [i] while (kthChild (i, 1)heap [rightChild]? leftChild: rightChild} / ** * Этот метод используется для печати всех элементов кучи * * / public void printHeap () {System.out.print ('nHeap =') for (int i = 0 i
На этом мы подошли к концу статьи о двоичной куче в Java. Проверьте    от Edureka, надежной компании по онлайн-обучению с сетью из более чем 250 000 довольных учащихся по всему миру. Курс обучения и сертификации по Java J2EE и SOA от Edureka предназначен для студентов и профессионалов, которые хотят стать Java-разработчиками. Курс разработан, чтобы дать вам хорошее начало в программировании на Java и обучить вас как основным, так и продвинутым концепциям Java, а также различным средам Java, таким как Hibernate и Spring. 
 Есть вопрос к нам? Пожалуйста, укажите это в разделе комментариев этого блога «Java ArrayList», и мы свяжемся с вами как можно скорее.