Implémenter le tas à l'aide d'un arbre binaire

À mettre en œuvre un tas avec un arbre binaire O(log n) le temps de la complexité, vous avez besoin pour stocker le nombre total de nœuds comme une variable d'instance.

Supposons que nous avons eu un tas de 10 nœuds.

Si nous devions ajouter un nœud...

On incrémente le nombre total de nœuds par un. Maintenant, nous avons 11 total des nœuds. Nous convertissons le nouveau nombre total de nœuds (11) à sa représentation binaire: 1011.

Avec la représentation binaire du total des nœuds (1011), nous nous débarrassons du premier chiffre. Par la suite, nous utilisons 011 pour naviguer dans l'arbre à l'emplacement suivant pour insérer un nœud. 0 signifie que pour aller à gauche et 1 signifie que pour aller à droite. Donc, avec 011, nous allons à gauche, allez à droite, et allez à droite...ce qui nous amène à la prochaine emplacement pour insérer dans.

Nous avons examiné un noeud par niveau, ce qui rend le temps de complexité O(log n)

En supposant que vous souhaitez utiliser un lié arbre binaire, avec pas de pointeurs vers les nœuds parents, alors la seule solution je pense est de garder un compteur de nombre d'enfants dans chaque nœud.

availableLeaf(node) {
    if( node.left is Empty || node.right is Empty )
        return node ;
    else
       if( node.left.count < node.right.count )
           return availableLeaf(node.left)
       else
           return availableLeaf(node.right)
}

Cette stratégie d'équilibre entre le nombre de nœuds de chaque côté de chaque sous-arbre, ce qui est bénéfique (mais très légèrement).

C'est O(log n). Garder la trace de compter sur l'insertion nécessite à venir tout le chemin jusqu'à la toiture, mais cela ne modifie pas l'O(lon n) la nature de cette opération. Même chose avec la suppression.

Les autres opérations sont à l'habitude, et de préserver leurs caractéristiques de performance.

Avez-vous besoin de détails ou si vous préférez travailler par vous-même?

Si vous souhaitez utiliser un lié arbre binaire, sans autres informations que celles de gauche et de droite pointeurs, alors je vous suggère de lancer une prime pour au moins 100 000 points. Je ne dis pas que c'est impossible (parce que je n'ai pas les maths pour le prouver), mais je dis que cela n'a pas été trouvé dans plusieurs décennies (dont je ne sais plus).

De l'arbre binaire peut être représenté par un tableau:

import java.util.Arrays;
public class MyHeap {
private Object[] heap;
private int capacity;
private int size;
public MyHeap() {
capacity = 8;
heap = new Object[capacity];
size = 0;
}
private void increaseCapacity() {
capacity *= 2;
heap = Arrays.copyOf(heap, capacity);
}
public int getSize() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
public Object top() {
return size > 0 ? heap[0] : null;
}
@SuppressWarnings("unchecked")
public Object remove() {
if (size == 0) {
return null;
}
size--;
Object res = heap[0];
Object te = heap[size];
int curr = 0, son = 1;
while (son < size) {
if (son + 1 < size
&& ((Comparable<Object>) heap[son + 1])
.compareTo(heap[son]) < 0) {
son++;
}
if (((Comparable<Object>) te).compareTo(heap[son]) <= 0) {
break;
}
heap[curr] = heap[son];
curr = son;
son = 2 * curr + 1;
}
heap[curr] = te;
return res;
}
@SuppressWarnings("unchecked")
public void insert(Object e) {
if (size == capacity) { //auto scaling
increaseCapacity();
}
int curr = size;
int parent;
heap[size] = e;
size++;
while (curr > 0) {
parent = (curr - 1) / 2;
if (((Comparable<Object>) heap[parent]).compareTo(e) <= 0) {
break;
}
heap[curr] = heap[parent];
curr = parent;
}
heap[curr] = e;
}
}

Utilisation:

    MyHeap heap = new MyHeap(); //it is a min heap
heap.insert(18);
heap.insert(26);
heap.insert(35);
System.out.println("size is " + heap.getSize() + ", top is " + heap.top());
heap.insert(36);
heap.insert(30);
heap.insert(10);
while(!heap.isEmpty()) {
System.out.println(heap.remove());
}