Búsqueda en Arreglos y Heaps: Preguntas Frecuentes

Búsqueda en Arreglos

ind BLin(tabla T, dimension D, clave k) para i desde 0 hasta D–1: si T[i]==k: devolver i; devolver -1; //k no está en T

Búsqueda Binaria

ind BBin(tabla T, ind P, ind U, clave k) si P > U: // caso base dev -1 //Llamada errónea ó K no en T si no: M= (P + U) / 2 //División entera (floor) si k == T[M]: dev M si k

Preguntas Frecuentes sobre Heaps

¿Se puede utilizar un minHeap para ordenar valores de mayor a menor?

Sí. Se van extrayendo los valores y se van colocando en un vector de derecha a izquierda. Es decir, el primero que sale es el menor de todos (el heap es un minHeap), y se coloca al final del vector. Y así se van extrayendo elementos del heap y rellenando las posiciones del vector de derecha a izquierda, hasta extraer el último elemento del heap, que será el mayor de todos y quedará colocado en la primera posición del vector.

¿Cuál es la estructura de datos más eficiente para implementar el TAD Heap? ¿Por qué?

El array. Porque permite representar un árbol de modo que el acceso a los hijos y al padre de cada nodo, para trabajar con el Heap, sea inmediato. La raíz del heap ocupa la posición 0 del array. Los hijos de un nodo situado en la posición n del array ocupan las posiciones 2n+1 y 2n+2, y, para un nodo que ocupe la posición n en el array, su padre se encuentra en la posición (n-1)/2. De esta manera, el acceso a cada nodo durante las operaciones HeapifyUp y HeapifyDown es inmediato, y el intercambio de nodos en estas operaciones también (es intercambiar los valores que se encuentran en esas posiciones del array). Por tanto, es muy eficiente. En otras estructuras estudiadas en clase, como ABs, el acceso a los padres e hijos de un árbol y el intercambio de nodos no es tan inmediato, es más costoso.

¿Se puede implementar el TAD Heap con la estructura de datos basada en nodos utilizada en clase para implementar ABs?

No, porque no se tiene acceso directo al padre de cada nodo, aunque sí se podría utilizar si se implementara una función que, dado un nodo, buscara su padre recorriendo el árbol, pero sería muy poco eficiente, porque los algoritmos de manejo de heaps están constantemente accediendo a padres e hijos… Otra solución sería incorporar un campo “father” al nodo, para poder tener acceso directo el padre de un nodo mediante un puntero directo, pero las operaciones HeapifyUp y HeapifyDown serían igualmente más costosas que utilizando un array, pues requerirían el intercambio de varios punteros cada vez que se intercambiara un padre con un hijo (punteros padre, izq y der para cada nodo intercambiado). Nota: en esta pregunta, se han considerado bien las respuestas Sí y No, siempre que se hayan argumentado correctamente.