Разберете как да внедрите двоична купчина в Java

Тази статия ще ви даде пълен преглед на работата на сортирането на купчини и по-късно ще се научим да прилагаме двоична купчина в Java.

Ето дневния ред на тази статия:

1. Какво е сортиране на купчина?
2. Max Heap
3. Мин куп
4. Внедряване на купчина в Java
   • Диаграма
   • Код

Нека да започнем!

Какво е сортиране на купчина?

Heap е основно дървовидна структура от данни. Той има възли. Възелът се състои от определени елементи. Всеки възел съдържа един елемент.

Възлите могат да имат деца. Ако в случай че няма деца, това се нарича Лист.

сортира масив c ++ възходящ

Трябва да се спазват две правила:

• Стойността на всеки възел трябва да бъде по-малка или равна на всички стойности, съхранявани в неговите дъщери.
• Той има възможно най-малката височина.

Купчините са изключително ефективни при извличането нанай-малък или най-голям елемент.

Нека да преминем към минната купчина сега!

Мин куп

Min heap е пълно двоично дърво, в което стойността на елемента root е по-малка или равна на който и да е от дъщерните елементи.

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

Arr [(i-1) / 2]: това ще върне родителския възел.

Arr [(2 * i) + 1]: това ще върне левия детски възел.

Arr [(2 * i) + 2]: това ще върне правилния дъщерен възел.

Има определени методи на Min Heap:

• вмъкване (): Добавен е нов ключ в края на дървото. В случай, че новият ключ е по-голям от родителя, няма нужда да правите нищо, в противен случай трябва да преминем, за да настроим свойствата на купчината.
• getMin (): този метод помага да се върне основния елемент.
• extractMin (): този метод връща минимумаелемент.

Преминаване към Max heap сега.

пролетен mvc урок за начинаещи

Максимална купчина

Max heap е пълно двоично дърво, в което стойността на елемента root е по-голяма или равна на всеки от дъщерния елемент.

Max heap също се състои от няколко метода!

• Вмъкване (): той ще вмъкне елемент в купчината.
• Изтрий() : ще изтрие елемент от купчината.
• FindMax (): ще намери максималния елемент от купчината.
• printHeap (): Ще отпечата съдържанието на купчината

Сега нека ви покажа изпълнението на купчината чрез диаграма и по-късно Javaкод.

Внедряване на купчина в Java

Диаграма:

Диаграмата по-горе показва двоичната купчина в Java. Както разбрахте, че има две купчини: Мин куп и Макс куп, ето диаграма:

Сега, преминавайки към следващия ни сегмент, ще видим как да приложим двоична купчина в Java.

Код:

публичен клас 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 ()) хвърли нов NoSuchElementException ('Heap е пълен, няма място за вмъкване нов елемент ') heap [heapSize ++] = x heapifyUp (heapSize-1)} / ** * Това ще изтрие елемент с индекс x * Сложност: O (log N) * * / public int delete (int x) {if (isEmpty ()) хвърли нов NoSuchElementException ('Heap is empty, No element to delete') int key = heap [x] heap [x] = heap [heapSize -1] heapSize-- heapifyDown (x) retu rn ключ} / ** * Този метод, използван за поддържане на свойствата на купчината при вмъкване на елемент. * * / 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} / ** * Този метод, използван за поддържане на свойството heap при изтриване на елемент. * * / 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
С това стигнахме до края на тази статия за Binary Heap в Java. Вижте    от Edureka, доверена компания за онлайн обучение с мрежа от над 250 000 доволни учащи, разпространени по целия свят. Курсът за обучение и сертифициране на Java J2EE и SOA на Edureka е предназначен за студенти и професионалисти, които искат да бъдат Java Developer. Курсът е предназначен да ви даде начален старт в програмирането на Java и да ви обучи както за основни, така и за разширени Java концепции, заедно с различни Java рамки като Hibernate & Spring. 
 Имате въпрос към нас? Моля, споменете го в раздела за коментари в този блог „Java ArrayList“ и ние ще се свържем с вас възможно най-скоро.