Juan Camilo Muñoz Castelblanco

Ejercicios de la lectura 6

Solve exercises 6.5-3, 6.5-8 and problem 6.1 form CLRS

        

Exercise 6.5-3

Write pseudocode for the procedures HEAP-MINIMUM, HEAP-EXTRACT-MIN, HEAPDECREASE-KEY, and MIN-HEAP-INSERT that implement a min-priority queue with a min-heap.

 

HEAP-MINIMUM(A)

return A[1]

 

HEAP-EXTRACT-MIN(A)

if heap-size[A] < 1 then mostrar mensaje de error

min ←A[1]

A[1] ← A[heap-size[A]]

heap-size[A] ← heap-size[A]-1

MIN-HEAPIFY(A,1)

return min

 

HEAP-DECREASE-KEY(A,i,key)

if key > A[i] then mostrar mensaje de error

A[i] ← key

while i > 1 and A[parent(i)] > A[i] do

swap A[i] and A[parent(i)]

i ← parent(i)

 

MIN-HEAP-INSERT(A,key)

heap-size[A] ← heap-size[A]+1

A[heap-size[A]] ← largest integer

HEAP-DECREASE-KEY(A,heap-size[A],key)

 

 

 

        

 

Exercise 6.5-8

Give an O(n lg k)-time algorithm to merge k sorted lists into one sorted list, where n is the total number of elements in all the input lists. (Hint: Use a min-heap for k-way merging.)

Dadas k listas almacenadas con un total de n elementos se combinan con merge que sabemos es de tiempo de O(n lg k). Luego se insertan todos los k elementos de la posición 1 de cada lista en la pila.

Usando EXTRACT-MAX obtenemos el primer elemento de la lista combinada. Insertamos el elemento en la segunda posición desde la lista donde el elemento mas grande originalmente viene de la pila.

Continuando el mismo procedimiento tenemos el algoritmo deseado que claramente es de orden O(n lg k).

PROBLEM 6-1

·  Los procedimientos BUIL-MAX-HEAP y BUIL-MAX-HEAP’ no siempre crean la misma pila cuando lo corremos con un mismo array de entrada. Consideremos el siguiente contra-ejemplo:

Entrada: Array A:

BUIL-MAX-HEAP(A)

BUIL-MAX-HEAP’(A)

·  Usando un límite superior de tiempo O (n lg n) que comience de n -1 y que llame a MAX-HEAP-INSERT, cada llamada es de orden O (lg n ). Para la cota inferior de , consideremos el caso en el que el array de entrada está dado en orden estrictamente incremental

Cada llamada a MAX-HEAP-INSERT produce HEAP-INCREASE-KEY y va por cualquier camino a la raíz. Desde la profundidad del nodo , el tiempo total es:

En el peor de los casos por lo tanto BUILD-MAX-HEAP’ requiere  para construir un heap de n elementos.