- ความสมบูรณ์. ทุกระดับของต้นไม้ประกอบด้วยโหนดที่เป็นไปได้ทั้งหมด ยกเว้นโหนดสุดท้าย ซึ่งสามารถเติมได้เพียงบางส่วนเท่านั้น และเติมจากซ้ายไปขวา
- ปิระมิดมักจะถูกนำมาใช้ตามอาเรย์
- สำหรับแต่ละโหนดในปิรามิด มีเงื่อนไขพื้นฐานว่าค่าของแต่ละโหนดมากกว่า (หรือเท่ากับ) ค่าของลูกหลาน ดังนั้นค่าสูงสุดจะถูกเก็บไว้ในองค์ประกอบด้านบน

การลบองค์ประกอบตามดัชนี
ขั้นแรก มาดูลำดับการดำเนินการเมื่อลบโหนดที่เลือก:- ลบโหนดที่เลือก
- ย้ายโหนดสุดท้ายในแถวสุดท้ายไปยังตำแหน่งของโหนดที่ถูกลบ
- เลื่อนลงจนกระทั่งอยู่ด้านล่างโหนดที่ใหญ่กว่าและเหนือโหนดที่เล็กกว่า
-
เราลบโหนดที่เลือกและแทนที่โหนดสุดท้ายซึ่งมีค่าเป็น 4:
แต่ในตำแหน่งนี้โหนดนี้ไม่ตรงตามเงื่อนไขที่โหนดลูกหลานแต่ละโหนดไม่ควรใหญ่กว่าโหนดที่เป็นปัญหาใช่ไหม?
นั่นเป็นเหตุผล:
-
เราสลับมันกับลูกที่ใหญ่ที่สุดซึ่งมีค่าเป็น 6:
ต่อไป เราจะดูว่ามีการสืบทอดที่มีค่ามากกว่าองค์ประกอบที่ถูกแทนที่ของเราหรือไม่ และเราเห็นว่าไม่มีเลย ซึ่งหมายความว่าองค์ประกอบนั้นได้เข้ามาแทนที่แล้ว
การแทรกองค์ประกอบใหม่
การดำเนินการเมื่อแทรกองค์ประกอบใหม่มีอะไรบ้าง:-
โหนดที่แทรกไว้จะถูกวางไว้ที่ส่วนท้ายของปิรามิด
แต่เรามีเงื่อนไขว่าองค์ประกอบลูกไม่สามารถมีค่ามากกว่าองค์ประกอบแม่ได้ใช่ไหม
นั่นเป็นเหตุผล:
- เปรียบเทียบองค์ประกอบใหม่กับองค์ประกอบหลัก หากองค์ประกอบใหม่มีขนาดเล็กลง แสดงว่าการดำเนินการเสร็จสิ้น ถ้าไม่เช่นนั้น การดำเนินการจะสลับตำแหน่งกับองค์ประกอบหลัก หลังจากนั้นจะเริ่มเปรียบเทียบกับองค์ประกอบหลักใหม่ เป็นต้น... จนกว่าองค์ประกอบหลักจะยิ่งใหญ่กว่าองค์ประกอบใหม่
-
วางโหนดใหม่ที่ส่วนท้ายของปิรามิด:
-
เปรียบเทียบองค์ประกอบใหม่กับองค์ประกอบหลักซึ่งมีค่าเป็น 4
เนื่องจากองค์ประกอบใหม่มีขนาดใหญ่กว่าองค์ประกอบหลัก เราจึงสลับองค์ประกอบเหล่านี้:
-
เราเปรียบเทียบองค์ประกอบใหม่กับพาเรนต์ใหม่และพบว่าองค์ประกอบของเรามีขนาดใหญ่กว่า (8>7) ดังนั้นเราจึงสลับองค์ประกอบเหล่านั้นด้วย:
อีกครั้ง เราเปรียบเทียบองค์ประกอบกับองค์ประกอบหลัก และเห็นว่าคราวนี้องค์ประกอบหลักมีขนาดใหญ่ขึ้น ซึ่งหมายความว่าองค์ประกอบใหม่ของเราเข้าที่แล้ว
การแทนที่องค์ประกอบ
เมื่อเปลี่ยนองค์ประกอบ คุณต้องแทนที่องค์ประกอบด้วยดัชนีที่กำหนดก่อน ตรรกะใช่มั้ย? แล้วไงต่อ? ท้ายที่สุดแล้ว ค่าใหม่ขององค์ประกอบนั้นแตกต่างออกไปแล้ว และมันไม่สอดคล้องกับเงื่อนไขของปิรามิด นั่นคือ ไม่ใช่ความจริงที่ว่าองค์ประกอบลูกทั้งหมดมีขนาดเล็กกว่าองค์ประกอบที่แทรกเข้าไป ไม่ใช่ความจริงที่ว่าองค์ประกอบหลักมีขนาดใหญ่กว่าองค์ประกอบใหม่ ดังนั้นก่อนอื่นคุณต้องเปรียบเทียบกับค่าเก่าขององค์ประกอบ:- หากองค์ประกอบใหม่มีขนาดใหญ่กว่านั้น เราจำเป็นต้องเปรียบเทียบกับองค์ประกอบหลัก และหากจำเป็น ให้สลับองค์ประกอบเหล่านั้น
- หากองค์ประกอบใหม่มีขนาดเล็กลง จะต้องเปรียบเทียบกับองค์ประกอบย่อยที่ใหญ่กว่า และสลับหากองค์ประกอบย่อยมีขนาดใหญ่กว่า (จนกว่าองค์ประกอบใหม่จะอยู่ในตำแหน่งที่ถูกต้อง)
- แทรกองค์ประกอบแทนที่องค์ประกอบก่อนหน้า:
- เราเปรียบเทียบองค์ประกอบก่อนหน้า 9 และองค์ประกอบใหม่ 1 และเห็นว่ามีขนาดเล็กกว่า ซึ่งหมายความว่าเราจะพยายามเลื่อนมันลง
- เราเปรียบเทียบกับองค์ประกอบที่ใหญ่ที่สุดจากลูก ๆ นั่นคือกับองค์ประกอบที่มีค่า 5 และเราเห็นว่าองค์ประกอบใหม่มีขนาดเล็กลง ดังนั้นเราจึงสลับองค์ประกอบที่เปรียบเทียบ:
- เนื่องจากตอนนี้ไม่มีองค์ประกอบใหม่ด้านล่างองค์ประกอบใหม่ของเรา เราสามารถพูดได้ว่าองค์ประกอบนั้นเข้าที่แล้ว
การดำเนินการปิรามิดใน Java
หลังจากทำความเข้าใจวิธีการทำงานของโครงสร้างนี้แล้ว ก็ถึงเวลาดูการใช้งานปิรามิดใน Java : คลาสที่แสดงถึงจุดยอดหนึ่งจุดและค่าที่มีอยู่:public class Node {
private int value;
public Node(int value) {
this.value = value;
}
public int getValue() {
return this.value;
}
public void setValue(int value) {
this.value = value;
}
}
คลาสที่เป็นตัวแทนของปิรามิดนั้น:
public class Heap {
private Node[] heapArray; // массив со всеми вершинами
private int maxSize; // размер массива
private int currentSize; // количество узлов массиве
public Heap(int maxSize) { // создание пустой пирамиды
this.maxSize = maxSize;
this.currentSize = 0;
heapArray = new Node[maxSize];
}
public void printHeap() { // отображение перамиды в консоль
System.out.println("Массив значений: ");
for (int n = 0; n < currentSize; n++) {
if (heapArray[n] != null) {
System.out.println(heapArray[n].getValue() + " ");
}
else {
System.out.println("-");
}
}
System.out.println();
int countOfGaps = 32;
int itemsPerRow = 1;
int columnNumber = 0; // номер element в данной строке
String lines = "___________________________________________________________________";
System.out.println(lines);
for (int i = 0; i < currentSize; i++) {
if (columnNumber == 0) { // проверяем первый элемент ли в текущей строке
for (int k = 0; k < countOfGaps; k++) { // добавляем предшествующие пробелы
System.out.print(' ');
}
}
System.out.print(heapArray[i].getValue());// выводим в консоль meaning вершины
if (++columnNumber == itemsPerRow) { // проверяем последний ли элемент в строке
countOfGaps /= 2; // уменьшаем количество оступов применяемое для следующей строки
itemsPerRow *= 2; // указываем, что элементов может быть вдвое больше
columnNumber = 0; // сбрасываем счётчик для текущего element строки
System.out.println(); // переходим на нову строку
}
else { //переход к следующему элементу
for (int k = 0; k < countOfGaps * 2 - 2; k++) {
System.out.print(' '); // добавляем оступы
}
}
}
System.out.println("\n" + lines); // нижний пункир
}
public boolean insertNode(int value) { // вставка нового значения
if (currentSize == maxSize) { // проверяем не выходим ли мы за рамки массива
return false;
}
Node newNode = new Node(value);// создание вершины с данным meaningм
heapArray[currentSize] = newNode;// вершину задём в самый низ дерева
displaceUp(currentSize++);// пытаемся поднять вершину, если meaning вершины позволяет
return true;
}
public Node removeNode(int index) { // удалить элемент по индексу массива
if(index > 0 && currentSize > index) {
Node root = heapArray[index];
heapArray[index] = heapArray[--currentSize]; // задаём элементу с переданным индексом, meaning последнего element
heapArray[currentSize] = null;// последний элемент удаляем
displaceDown(index);// проталкиваем вниз новый элемент, чтобы он должное ему место
return root;
}
return null;
}
public boolean changeNode(int index, int newValue) {
if (index < 0 || currentSize<=index) {
return false;
}
int oldValue = heapArray[index].getValue(); // сохраняем старое meaning
heapArray[index].setValue(newValue); // присваиваем новое
if (oldValue < newValue) {// если узел повышается
displaceUp(index); // выполняется смещение вверх
}
else { // если понижается
displaceDown(index); // смещение вниз
}
return true;
}
private void displaceUp(int index) { //смещение вверх
int parentIndex = (index - 1) / 2; // узнаем индекс родителя
Node bottom = heapArray[index]; // берем элемент
while (index > 0 && heapArray[parentIndex].getValue() < bottom.getValue()) {// если родительский элемент меньше
heapArray[index] = heapArray[parentIndex];// то меняем его местами с рассматриваемым
index = parentIndex;
parentIndex = (parentIndex - 1) / 2;// берем новый родительский индекс и повторяем сравнение элементов
}
heapArray[index] = bottom;// соохраняем результат
}
private void displaceDown(int index) {// смещение вниз
int largerChild;
Node top = heapArray[index]; // сохранение корня, пока у узла есть хотя бы один потомок
while (index < currentSize / 2) {// если данное condition не выполняется то элемент уже в самом низу пирамиды
int leftChild = 2 * index + 1; // вычисляем индексы в массиве для левого узла ребенка
int rightChild = leftChild + 1;// и правого
if (rightChild < currentSize && heapArray[leftChild].getValue() < heapArray[rightChild].getValue()) {
largerChild = rightChild;
}// вычисляем ребенка вершину с наибольшим числовым meaningм
else {
largerChild = leftChild;
}
if (top.getValue() >= heapArray[largerChild].getValue()) {// если meaning вершины больше or равно
//значени его наибольшего ребенка
break;// то выходим из метода
}
heapArray[index] = heapArray[largerChild];// заменяем вершину, большей дочерней вершиной
index = largerChild; // текущий индекс переходит вниз
}
heapArray[index] = top; // задаем конечное местоположение для element
}
}
สุดท้ายนี้ เรามาดูการทำงานของปิรามิดของเรากัน:
public class Solution {
public static void main(String[] args) {
// задаем начальные данные:
Heap heap = new Heap(31);
heap.insertNode(120);
heap.insertNode(40);
heap.insertNode(50);
heap.insertNode(80);
heap.insertNode(20);
heap.insertNode(100);
heap.insertNode(150);
heap.insertNode(30);
heap.insertNode(210);
heap.insertNode(180);
heap.insertNode(10);
heap.insertNode(90);
// выводим начальную пирамиду в консоль
heap.printHeap();
เอาต์พุตคอนโซล:
// изменяем элемент под индексом 0 с 210 на 15, и выводим в консоль измененную пирамиду
heap.changeNode(0,15);
heap.printHeap();
เอาต์พุตคอนโซล:
// удаляем элемент под индексом 3, который имеет meaning 80 и смотрим на изменившуюся пирамиду
heap.removeNode(3);
heap.printHeap();
}
}
เอาต์พุตคอนโซล: 


GO TO FULL VERSION