La construction d'un min tas à l'aide de java

Insérer :
Lorsque nous insérer dans un min-tas, on commence toujours par l'insertion de l'élément en bas. Nous insérer à la
a droite à l'endroit de façon à maintenir la complète de l'arbre de la propriété.
Ensuite, nous "réparer" l'arbre par le remplacement de l'élément nouveau, avec ses parents, jusqu'à ce que nous trouver un endroit approprié pour
l'élément. Nous avons essentiellement bulle de l'élément minimum.
Cela prend 0 (log n) fois, où n est le nombre de nœuds dans le tas.

Extrait D'Élément Minimum :
Trouver l'élément minimum de un min-tas est simple: c'est toujours au top. La partie la plus difficile est de savoir comment l'enlever
c'. (Je n fait, ce n'est pas que difficile.)
D'abord, on supprime l'élément minimum et il échange avec le dernier élément dans le tas (le dernier,
plus à droite de l'élément). Ensuite, nous avons bulle en bas de cet élément, en l'échangeant avec un de ses enfants jusqu'à ce que le minheap
la propriété est restaurée.
Nous ne remplacez-la par la gauche de l'enfant ou le droit de l'enfant? Qui dépend de leurs valeurs. Il n'y a pas inhérente
commande entre la gauche et la droite de l'élément, mais vous aurez besoin de prendre le plus petit dans le but de maintenir
le min de segment de mémoire de la commande.

public class MinHeap {
private int[] heap;
private int size;
private static final int FRONT = 1;
public MinHeap(int maxSize) {
heap = new int[maxSize + 1];
size = 0;
}
private int getParent(int position) {
return position / 2;
}
private int getLeftChild(int position) {
return position * 2;
}
private int getRightChild(int position) {
return position * 2 + 1;
}
private void swap(int position1, int position2) {
int temp = heap[position1];
heap[position1] = heap[position2];
heap[position2] = temp;
}
private boolean isLeaf(int position) {
if (position > size / 2) {
return true;
}
return false;
}
public void insert(int data) {
heap[++size] = data;
int currentItemIndex = size;
while (heap[currentItemIndex] < heap[getParent(currentItemIndex)]) {
swap(currentItemIndex, getParent(currentItemIndex));
currentItemIndex = getParent(currentItemIndex);
}
}
public int delete() {
int item = heap[FRONT];
swap(FRONT, size--); //heap[FRONT] = heap[size--];
heapify(FRONT);
return item;
}
private void heapify(int position) {
if (isLeaf(position)) {
return;
}
if (heap[position] > heap[getLeftChild(position)]
|| heap[position] > heap[getRightChild(position)]) {
//if left is smaller than right
if (heap[getLeftChild(position)] < heap[getRightChild(position)]) {
//swap with left
swap(heap[position], heap[getLeftChild(position)]);
heapify(getLeftChild(position));
} else {
//swap with right
swap(heap[position], heap[getRightChild(position)]);
heapify(getRightChild(position));
}
}
}
@Override
public String toString() {
StringBuilder output = new StringBuilder();
for (int i = 1; i <= size / 2; i++) {
output.append("Parent :" + heap[i]);
output
.append("LeftChild : " + heap[getLeftChild(i)] + " RightChild :" + heap[getRightChild(i)])
.append("\n");
}
return output.toString();
}
public static void main(String... arg) {
System.out.println("The Min Heap is ");
MinHeap minHeap = new MinHeap(15);
minHeap.insert(5);
minHeap.insert(3);
minHeap.insert(17);
minHeap.insert(10);
minHeap.insert(84);
minHeap.insert(19);
minHeap.insert(6);
minHeap.insert(22);
minHeap.insert(9);
System.out.println(minHeap.toString());
System.out.println("The Min val is " + minHeap.delete());
}
}