Básicamente, la declaración citada se refiere al problema de resolver la ubicación para la inserción y eliminación de elementos de datos en y desde el montón. Para mantener "la propiedad de forma" de un montón binario, el nivel más bajo del montón siempre debe llenarse de izquierda a derecha sin dejar nodos vacíos. Para mantener los tiempos medios de inserción y eliminación de O (1) para el montón binario, debe poder determinar la ubicación para la siguiente inserción y la ubicación del último nodo en el nivel más bajo para usar para eliminar el nodo raíz, ambos en tiempo constante.
Para un montón binario almacenado en una matriz (con su estructura de datos compactada implícita como se explica en la entrada de Wikipedia), esto es fácil. Simplemente inserte el miembro de datos más nuevo al final de la matriz y luego "burbuja" en su posición (siguiendo las reglas de montón). O reemplace la raíz con el último elemento de la matriz "burbujeando hacia abajo" para eliminar. Para los montones en el almacenamiento de matriz, la cantidad de elementos en el montón es un puntero implícito al lugar donde se insertará el siguiente elemento de datos y dónde encontrar el último elemento que se utilizará para eliminación.
Para un montón binario almacenado en una estructura en árbol, esta información no es tan obvia, pero dado que es un árbol binario completo, se puede calcular. Por ejemplo, en un árbol binario completo con 4 elementos, el punto de inserción siempre será el hijo correcto del hijo izquierdo del nodo raíz. El nodo que se utilizará para la eliminación siempre será el hijo izquierdo del hijo izquierdo del nodo raíz. Y para cualquier tamaño de árbol arbitrario dado, el árbol siempre tendrá una forma específica con puntos de inserción y eliminación bien definidos. Como el árbol es un "árbol binario completo" con una estructura específica para cualquier tamaño dado, es muy posible calcular la ubicación de la inserción/eliminación en el tiempo O (1). Sin embargo, la trampa es que incluso cuando sabes dónde está estructuralmente, no tienes idea de dónde estará el nodo en la memoria. Por lo tanto, debe atravesar el árbol para llegar al nodo determinado, que es un proceso O (log n) que hace que todas las inserciones y eliminaciones sean un mínimo de O (log n), rompiendo el comportamiento O (1) que se desea normalmente. Cualquier búsqueda ("primero en profundidad", o alguna otra) será al menos O (log n) también debido al problema transversal observado y, por lo general, O (n) debido a la naturaleza aleatoria del montón semiorreginado.
El truco es ser capaz tanto de calcular y referencia aquellos inserción/puntos de deleción en tiempo constante, ya sea mediante el aumento de la estructura de datos ("enhebrar" el árbol, como se menciona en el artículo de Wikipedia) o el uso adicional punteros.
La implementación que me parece más fácil de entender, con poca memoria y sobrecarga de codificación adicional, es simplemente usar una estructura de árbol binario simple normal (usando pRoot y Node definidos como [data, pParent, pLeftChild, pRightChild]) y agrega dos punteros adicionales (pInsert y pLastNode). pInsert y pLastNode se actualizarán durante las subrutinas de inserción y eliminación para mantenerlos actualizados cuando cambien los datos dentro de la estructura. Esta implementación le da a O (1) acceso tanto al punto de inserción como al último nodo de la estructura y debe permitir la preservación del comportamiento general de O (1) tanto en la inserción como en la eliminación. El costo de la implementación es de dos punteros adicionales y un pequeño código extra en las subrutinas de inserción/eliminación (también conocido como mínimo).
EDITAR: pseudocódigo añadido para un O (1) insertar()
Aquí es pseudo código para una subrutina de inserto que es O (1), en promedio:
define Node = [T data, *pParent, *pLeft, *pRight]
void insert(T data)
{
do_insertion(data); // do insertion, update count of data items in tree
# assume: pInsert points node location of the tree that where insertion just took place
# (aka, either shuffle only data during the insertion or keep pInsert updated during the bubble process)
int N = this->CountOfDataItems + 1; # note: CountOfDataItems will always be > 0 (and pRoot != null) after an insertion
p = new Node(<null>, null, null, null); // new empty node for the next insertion
# update pInsert (three cases to handle)
if (int(log2(N)) == log2(N))
{# #1 - N is an exact power of two
# O(log2(N))
# tree is currently a full complete binary tree ("perfect")
# ... must start a new lower level
# traverse from pRoot down tree thru each pLeft until empty pLeft is found for insertion
pInsert = pRoot;
while (pInsert->pLeft != null) { pInsert = pInsert->pLeft; } # log2(N) iterations
p->pParent = pInsert;
pInsert->pLeft = p;
}
else if (isEven(N))
{# #2 - N is even (and NOT a power of 2)
# O(1)
p->pParent = pInsert->pParent;
pInsert->pParent->pRight = p;
}
else
{# #3 - N is odd
# O(1)
p->pParent = pInsert->pParent->pParent->pRight;
pInsert->pParent->pParent->pRight->pLeft = p;
}
pInsert = p;
// update pLastNode
// ... [similar process]
}
Así, insert (T) es O (1) en promedio: exactamente O (1) en todos los casos, excepto cuando el árbol debe incrementarse en un nivel cuando es O (log N), lo que ocurre en cada log N inserciones (suponiendo que no hay eliminaciones) . La adición de otro puntero (pLeftmostLeaf) podría hacer insert() O (1) para todos los casos y evitar el posible caso patológico de inserción alternada & en un árbol binario completo completo. (Agregar pLeftmost se deja como un ejercicio [es bastante fácil].)
@Yse: es su pregunta "¿Cómo puedo encontrar el último elemento de un montón binario"? –
Usa 2 montones, o (peor porque pierde O (1) inserción de avarage) un montón binario y haz un seguimiento de los más grandes y pequeños: http://stackoverflow.com/questions/7878622/can-we-use-binary-search -tree-to-simulate-heap-operation –