Estructura de Datos : Clasificación HeapSort

Definiciones

Las condiciones iniciales son las siguientes :

El archivo a clasificar ya está en memoria, dispuesto en slots contiguos.
Los registros del archivo los denominaremos R1, R2, R3, ..., Ri, ..., Rn donde 1=< i =< n.
Existen en memoria n slots, donde en cada uno de ellos se dispone un registro del archivo a clasificar.
Todos los registros tienen una clave Ki, donde i es 1 =< i =< n.
Los registros están desordenados respecto de la clave mencionada.
La clasificación será hecha valiéndose de almacenamiento adicional, de cantidad fija.

La secuencia de acciones es la siguiente :

Se interpretará el archivo a ser clasificado como un árbol binario completo, dispuesto secuencialmente en los n slots de memorias que se mencionaron en las condiciones iniciales del punto anterior. Valen entonces las reglas de ubicación de las posiciones del padre y los hijos isquierdo y derecho, a partir de la posición de un nodo, desarrolados en la estructura de datos árboles binarios representados secuencialmente.
Se carga el archivo como un árbol binario completo con representación secuencial. Llamaremos a esta estructura de datos árbol inicial. Está claro que se ocupan todos los slots en forma contínua.
Se convierte el árbol inicial en un árbol binario completo que llamaremos árbol heap. Heap en inglés significa : montón, amontonar y apilar. Un árbol heap se define como un árbol binario completo donde el valor de cada nodo es tan grande, mayor o igual, que el valor de cada uno de sus hijos, si estos existen. Esta formulación implica que el valor más alto reside en el nodo raíz del árbol heap. Este árbol heap, así convertido, lo llamaremos heap inicial.
En un proceso repetitivo se arma la secuencia de valores en órden decreciente. Se lo hace de a un valor por vez. Para obtener un nuevo valor, ordenado decrecientemente, deben ejecutarse las siguientes acciones :
- Se retira el nodo raíz del árbol heap y se lo almacena en una lista. Queda entonces un árbol remanente con n -1 nodos, que llamaremos árbol remanente n-1.
- Se restructura el árbol remanente n-1, como un nuevo árbol heap, al que llamaremos árbol heap n-1.
- Se continúa con esta tarea, reiteradamente, hasta que el árbol remanente que se obtenga sea un árbol vacío. En ese momento estaríamos en presencia del árbol remanente n-n.

La secuencia seria entonces :

Armo arbol inicial
Armo arbol heap n
Retiro valor mayor
Armo arbol heap n - 1
Retiro valor mayor
Armo arbol heap n - 2
Retiro valor mayor
.........
.........
.........
.........
Armo arbol heap 2
Retiro valor mayor
Armo arbol heap 1
Retiro valor mayor
Armo arbol heap 0
Retiro valor mayor

En este algoritmo usaremos :

Arreglos
Arboles binarios con representacion secuencial
Arboles binarios con representacion enlazada

   Archivo, Registros y Claves

              R1   R2   R3             Ri             Rn
   ........------------------.......--------.......--------.......
            | K1 | K2 | K3 |         | Ki |         | Kn |              n slots       Input File
   ........------------------.......--------.......--------.......


   Reglas de ubicacion de padres e hijos en la representacion secuecial de arboles

                Np                  Ni             Nl   Nr              Ni ( Nodo )               i
   ..........--------............--------.......------------......      Nl ( Nodo hijo left )     2 * i
              |    |              |    |         |    |    |            Nr ( Nodo hijo right )    2 * i + 1
   ..........--------............--------.......------------......      Np ( Nodo parent )        Piso i / 2


   Arbol heap

                        Padre
                        +----+
                        | pa |
                        +----+                    pa > hl
                         |  |
                +--------+  +--------+            pa > hr
                |                    |
              +----+              +----+          No importan los valores relativos de hl y hr
              | hl |              | hr |
              +----+              +----+
          Hijo Isquierdo       Hijo Derecho

Ejemplos

Ejemplo 1

En el ejemplo pueden observarse como evolucionan los árboles, para un archivo con 10 registros. En forma generica ( X1, X2, X3, ...., Xn-2, Xn-1, Xn ). En el ejemplo ( 26, 5, 77, 1, 61, 11, 59, 15, 48, 19 ).

                             *---*                                                     *---*                                                     *---*
                             |X 1|                                                     |2 6|                                                     |7 7|
                             *---*                                                     *---*                                                     *---*
                              | |                                                       | |                                                       | |
               +--------------+ +--------------+                         +--------------+ +--------------+                         +--------------+ +--------------+
               |                               |                         |                               |                         |                               |
             *---*                           *---*                     *---*                           *---*                     *---*                           *---*
             |X 2|                           |X 3|                     | 5 |                           |7 7|                     |6 1|                           |5 9|
             *---*                           *---*                     *---*                           *---*                     *---*                           *---*
              | |                             | |                       | |                             | |                       | |                             | |
       +------+ +------+               +------+ +------+         +------+ +------+               +------+ +------+         +------+ +------+               +------+ +------+
       |               |               |               |         |               |               |               |         |               |               |               |
     *---*           *---*           *---*           *---*     *---*           *---*           *---*           *---*     *---*           *---*           *---*           *---*
     |X 4|           |X 5|           |X 6|           |X 7|     | 1 |           |6 1|           |1 1|           |5 9|     |4 8|           |1 9|           |1 1|           |2 6|
     *---*           *---*           *---*           *---*     *---*           *---*           *---*           *---*     *---*           *---*           *---*           *---*
      . .             .                                         | |             |                                         | |             |
   .... ....       ....                                      +--+ +--+       +--+                                      +--+ +--+       +--+
   .       .       .                                         |       |       |                                         |       |       |
 *---*   *---*   *---*                                     *---*   *---*   *---*                                     *---*   *---*   *---*
 |   |   |   |   |   |                                     |1 5|   |4 8|   |1 9|                                     |1 5|   | 1 |   | 5 |
 *---*   *---*   *---*                                     *---*   *---*   *---*                                     *---*   *---*   *---*
 X n-2   X n-1    X n
                         Arbol Completo                                            Arbol Inicial                                Heap Inicial ( Heap n - 0 ) ( Heap 10 )


                             *---*                                                     *---*                                                 *---*
                             |6 1|                                                     |5 9|                                                 |4 8|
                             *---*                                                     *---*                                                 *---*
                              | |                                                       | |                                                   | |
               +--------------+ +--------------+                         +--------------+ +--------------+                     +--------------+ +--------------+
               |                               |                         |                               |                     |                               |
             *---*                           *---*                     *---*                           *---*                 *---*                           *---*
             |4 8|                           |5 9|                     |4 8|                           |2 6|                 |1 9|                           |2 6|
             *---*                           *---*                     *---*                           *---*                 *---*                           *---*
              | |                             | |                       | |                             | |                   | |                             | |
       +------+ +------+               +------+ +------+         +------+ +------+               +------+ +------+     +------+ +------+               +------+ +------+
       |               |               |               |         |               |               |               |     |               |               |               |
     *---*           *---*           *---*           *---*     *---*           *---*           *---*           *---* *---*           *---*           *---*           *---*
     |1 5|           |1 9|           |1 1|           |2 6|     |1 5|           |1 9|           |1 1|           | 1 | |1 5|           | 5 |           |1 1|           | 1 |
     *---*           *---*           *---*           *---*     *---*           *---*           *---*           *---* *---*           *---*           *---*           *---*
      | |                                                       |
   +--+ +--+                                                 +--+
   |       |                                                 |
 *---*   *---*                                             *---*
 | 5 |   | 1 |                                             | 5 |
 *---*   *---*                                             *---*

                     Heap n - 1 ( Heap 9 )                                      Heap n - 2 ( Heap 8 )                                 Heap n - 3 ( Heap 7 )

                      Clasificados = 77                                         Clasificados = 61,77                                Clasificados = 59, 61, 77


                             *---*                                                     *---*                                                 *---*
                             |2 6|                                                     |1 9|                                                 |1 5|
                             *---*                                                     *---*                                                 *---*
                              | |                                                       | |                                                   | |
               +--------------+ +--------------+                         +--------------+ +--------------+                     +--------------+ +--------------+
               |                               |                         |                               |                     |                               |
             *---*                           *---*                     *---*                           *---*                 *---*                           *---*
             |1 9|                           |1 1|                     |1 5|                           |1 1|                 | 5 |                           |1 1|
             *---*                           *---*                     *---*                           *---*                 *---*                           *---*
              | |                             |                         | |                                                   |
       +------+ +------+               +------+                  +------+ +------+                                     +------+
       |               |               |                         |               |                                     |
     *---*           *---*           *---*                     *---*           *---*                                 *---*
     |1 5|           | 5 |           | 1 |                     | 1 |           | 5 |                                 | 1 |
     *---*           *---*           *---*                     *---*           *---*                                 *---*

                     Heap n - 4 ( Heap 6 )                                      Heap n - 5 ( Heap 5 )                                Heap n - 6 ( Heap 4 )

                 Clasificados = 48, 59, 61, 77                            Clasificados = 26, 48, 59, 61, 77                  Clasificados = 19, 26, 48, 59, 61, 77


                             *---*                                                    *---*                                                  *---*
                             |1 1|                                                    | 5 |                                                  | 1 |
                             *---*                                                    *---*                                                  *---*
                              | |                                                      |
               +--------------+ +--------------+                        +--------------+
               |                               |                        |
             *---*                           *---*                    *---*
             | 5 |                           | 1 |                    | 1 |
             *---*                           *---*                    *---*

                     Heap n - 7 ( Heap 3 )                                      Heap n - 8 ( Heap 2 )                                Heap n - 9 ( Heap 1 )

           Clasificados = 15, 19, 26, 48, 59, 61, 77               Clasificados = 11, 15, 19, 26, 48, 59, 61, 77        Clasificados = 5, 11, 15, 19, 26, 48, 59, 61, 77












                    Heap n - 10 ( Heap 0 )

       Clasificados = 1, 5, 11, 15, 19, 26, 48, 59, 61, 77

Funciones

ADJUST

El parámetro i es la posición del primer nodo del árbol.
El parámetro n es la posición del último nodo del árbol.

procedure ADJUST(i,n)

R <---- Ri
K <---- Ki
j <---- 2 * i
while j =< n
- do
  - Determino el mayor de los hijos
  - if j < n and Kj < Kj+1
    - then
      - j <---- j + 1
  - El padre es mayor que sus hijos - Nada debo cambiar
  - if K => Kj
    - then
      - p <---- piso de j/2
      - Rp <---- R
      - return
  - El padre es menor que sus hijos - Conmuto el padre
  - p <---- piso de j/2
  - Rp <---- Rj
  - j <---- 2 * j
- end
- p <---- piso de j/2
- Rp <---- R

end ADJUST

HSORT

El parámetro R es un archivo con registros R1, R2, ..., Rn.
El parámetro n es la cnatidad de registro del archivo R.

procedure HSORT(R,n)

i <---- piso n / 2
for i to 1 by -1
- do
  - call ADJUST(i,n)
- end
i <---- n - 1
for i to 1 by -1
- do
  - T <---- Ri+1
  - Ri+1 <---- R1
  - R1 <---- T
  - call ADJUST(1,i)
- end

end HSORT

                                                       piso de n/2
                                             +----------------------------+
                                             |                            |
                                             V                            |
              R1   R2   R3            Ri-1  Ri  Ri+1           Rn-2 Rn-1  Rn
   ........------------------.......------------------.......------------------.......
            |    |    |    |         |    |    |    |         |    |    |    |              n slots       Input File
   ........------------------.......------------------.......------------------.......

                                      Ajusto ............u................>
                                 Ajusto ..................................>



                  Ajusto .................................................>
             Ajusto ......................................................>
        Ajusto ...........................................................>



                                                                       n-1
                                                                      +---+
                                                                      |   |
                                                                      V   |
              R1   R2   R3            Ri-1  Ri  Ri+1           Rn-2 Rn-1  Rn
   ........------------------.......------------------.......------------------.......
            |    |    |    |         |    |    |    |         |    |    |    |              n slots       Input File
   ........------------------.......------------------.......------------------.......

        Ajusto ...........................................................>
        Ajusto ......................................................>
        Ajusto .................................................>



        Ajusto .........>
        Ajusto ....>