ESTRUCTURA DE DATOS Y ALGORITMOS

LABORATORIO N° 13
HEAP

Alumno Nota
Urquizo Apaza, Josue Alessandro
Grupo D
Fecha de Entrega 19/06/2023
Docente Renato Usnayo Cáceres

DISEÑO Y DESARROLLO DE SOFTWARE

PROGRAMA DE FORMACIÓN REGULAR
 Laboratorio de Estructura de Datos y Algoritmos Página | 1

OBJETIVOS:
• Conocer, comprender y aplicar el uso de Heap como una forma de almacenar datos en la
resolución de problemas de software.

SEGURIDAD:

Advertencia:
En este laboratorio está prohibida la manipulación del hardware, conexiones
eléctricas o de red; así como la ingestión de alimentos o bebidas.

FUNDAMENTO TEÓRICO:
• Revisar el texto guía que está en el campus Virtual.

NORMAS EMPLEADAS:
• No aplica

RECURSOS:
• En este laboratorio cada alumno trabajará con un equipo con Windows 10.

METODOLOGÍA PARA EL DESARROLLO DE LA TAREA:

• El desarrollo del laboratorio es individual.

PROCEDIMIENTO:
Nota:

Las secciones en cursivas son demostrativas, pero sirven para que usted pueda instalar las
herramientas de desarrollo en un equipo externo.

EJERCICIO DE APLICACIÓN

Introducción a los Heaps

Los heaps son estructuras de datos que se utilizan para almacenar y organizar elementos en función de
su valor. Son especialmente útiles cuando necesitamos acceder rápidamente al elemento de mayor o
menor valor.

En Python, los heaps se pueden implementar utilizando la biblioteca heapq. Esta biblioteca proporciona
una implementación eficiente de un heap binario.

DEPARTAMENTO DE TECNOLOGIA DIGITAL Y GESTION

 Laboratorio de Estructura de Datos y Algoritmos Página | 2

1. Importar la biblioteca heapq

Para comenzar, importaremos la biblioteca heapq en nuestro programa de Python:

import heapq

2. Crear un Heap Vacío

Para crear un heap vacío, podemos simplemente crear una lista vacía:

heap = []

3. Insertar elementos en el Heap

Podemos insertar elementos en el heap utilizando la función heapq.heappush():

heapq.heappush(heap, 5)
heapq.heappush(heap, 3)
heapq.heappush(heap, 8)

Después de insertar estos elementos, el heap se verá así: [3, 5, 8]. El elemento más pequeño siempre
estará en el índice 0 del heap.
import heapq
heap = []
heapq.heappush(heap, 5)
heapq.heappush(heap, 3)
heapq.heappush(heap, 8)

print(heap)

4. Obtener el elemento mínimo del Heap

Podemos obtener el elemento mínimo del heap utilizando la función heapq.heappop():

min_element = heapq.heappop(heap)
print(min_element)

import heapq
heap = []
heapq.heappush(heap, 5)
heapq.heappush(heap, 3)
heapq.heappush(heap, 8)

DEPARTAMENTO DE TECNOLOGIA DIGITAL Y GESTION

 Laboratorio de Estructura de Datos y Algoritmos Página | 3

min_element = heapq.heappop(heap)
print(min_element)

Después de extraer el elemento mínimo, el heap se verá así: [5, 8].

Mostrar una captura de la ejecución

import heapq

heap = []
heapq.heappush(heap, 5)
heapq.heappush(heap, 3)
heapq.heappush(heap, 8)

min_element = heapq.heappop(heap)
print(min_element)
print(heap)

5. Convertir una lista en un Heap

También podemos convertir una lista existente en un heap utilizando la función heapq.heapify():

lista = [7, 2, 9, 1, 4]
heapq.heapify(lista)
print(lista)

Mostrar una captura de la ejecución

Ejercicios Resueltos

Ejercicio 1: Encontrar los tres elementos más grandes

Dada una lista de números, encuentra los tres elementos más grandes utilizando un heap.

def find_largest_elements(nums):

DEPARTAMENTO DE TECNOLOGIA DIGITAL Y GESTION

 Laboratorio de Estructura de Datos y Algoritmos Página | 4

heap = []
for num in nums:
heapq.heappush(heap, num)
if len(heap) > 3:
heapq.heappop(heap)
return heap
lista_numeros = [12, 54, 23, 67, 45, 9, 41, 73]
largest_elements = find_largest_elements(lista_numeros)
print(largest_elements)

Mostrar una captura de la ejecución

import heapq

def find_largest_elements(nums):
heap = []
for num in nums:
heapq.heappush(heap, num)
if len(heap) > 3:
heapq.heappop(heap)
return heap

lista_numeros = [12, 54, 23, 67, 45, 9, 41, 73]

largest_elements = find_largest_elements(lista_numeros)
print("Los elementos mas grades son: ",largest_elements)

Ejercicio 2: Fusionar múltiples heaps

Dadas dos heaps, fusiona los dos heaps en uno solo.

def merge_heaps(heap1, heap2):

merged_heap = heap1 + heap2
heapq.heapify(merged_heap)
return merged_heap

heap1 = [2, 5, 8]
heap2 = [3, 6, 9]
merged_heap = merge_heaps(heap1, heap2)
print(merged_heap)

Mostrar una captura de la ejecución

DEPARTAMENTO DE TECNOLOGIA DIGITAL Y GESTION

 Laboratorio de Estructura de Datos y Algoritmos Página | 5

import heapq

def merge_heaps(heap1, heap2):

merged_heap = heap1 + heap2
heapq.heapify(merged_heap)
return merged_heap

heap1 = [2, 5, 8]
heap2 = [3, 6, 9]
merged_heap = merge_heaps(heap1, heap2)
print(merged_heap)

Ejecuta el siguiente código para obtener la lista ordenada

import heapq

def merge_heaps(heap1, heap2):

merged_heap = list(heapq.merge(heap1, heap2))
return merged_heap

heap1 = [2, 5, 8]
heap2 = [3, 6, 9]
merged_heap = merge_heaps(heap1, heap2)
print(merged_heap)

Mostrar una captura de la ejecución

import heapq

def merge_heaps(heap1, heap2):

merged_heap = list(heapq.merge(heap1, heap2))
return merged_heap

heap1 = [2, 5, 8]
heap2 = [3, 6, 9]
merged_heap = merge_heaps(heap1, heap2)
print(merged_heap)

Ejercicio 3: Ordenar una lista utilizando un heap

def heap_sort(lista):
heap = []

DEPARTAMENTO DE TECNOLOGIA DIGITAL Y GESTION

 Laboratorio de Estructura de Datos y Algoritmos Página | 6

for elemento in lista:

heapq.heappush(heap, elemento)

lista_ordenada = []
while heap:
lista_ordenada.append(heapq.heappop(heap))

return lista_ordenada

lista_desordenada = [9, 5, 2, 7, 1, 6]
lista_ordenada = heap_sort(lista_desordenada)
print(lista_ordenada) # Imprime: [1, 2, 5, 6, 7, 9]

Mostrar una captura de la ejecución

import heapq

def heap_sort(lista):
heap = []
for elemento in lista:
heapq.heappush(heap, elemento)

lista_ordenada = []
while heap:
lista_ordenada.append(heapq.heappop(heap))

return lista_ordenada

lista_desordenada = [9, 5, 2, 7, 1, 6]
lista_ordenada = heap_sort(lista_desordenada)
print(lista_ordenada)

Ejercicio 4: Implementar un Heap Máximo

Hasta ahora hemos trabajado con heaps mínimos, donde el elemento mínimo siempre está en el índice
0. Ahora, vamos a implementar un heap máximo donde el elemento máximo siempre estará en el índice
0.

import heapq

class MaxHeap:
def __init__(self):
self.heap = []

DEPARTAMENTO DE TECNOLOGIA DIGITAL Y GESTION

 Laboratorio de Estructura de Datos y Algoritmos Página | 7

def insert(self, elemento):

heapq.heappush(self.heap, -elemento)

def extract_max(self):
max_element = -heapq.heappop(self.heap)
return max_element

heap_max = MaxHeap()
heap_max.insert(5)
heap_max.insert(3)
heap_max.insert(8)
max_element = heap_max.extract_max()
print(max_element) # Imprime: 8

Mostrar una captura de la ejecución

import heapq

class MaxHeap:
def __init__(self):
self.heap = []

def insert(self, elemento):

heapq.heappush(self.heap, -elemento)

def extract_max(self):
max_element = -heapq.heappop(self.heap)
return max_element

heap_max = MaxHeap()
heap_max.insert(5)
heap_max.insert(3)
heap_max.insert(8)
max_element = heap_max.extract_max()
print(max_element)

Ejercicio 5: Encontrar el elemento k-ésimo más grande

Dada una lista de números y un número entero k, encuentra el elemento k-ésimo más grande utilizando
un heap.

def find_kth_largest(nums, k):

heap = []
for num in nums:

DEPARTAMENTO DE TECNOLOGIA DIGITAL Y GESTION

 Laboratorio de Estructura de Datos y Algoritmos Página | 8

heapq.heappush(heap, num)
if len(heap) > k:
heapq.heappop(heap)
return heapq.heappop(heap)

lista_numeros = [12, 54, 23, 67, 45, 9, 41, 73]

kth_largest = find_kth_largest(lista_numeros, 3)
print(kth_largest)

Mostrar una captura de la ejecución

import heapq

def find_kth_largest(nums, k):

heap = []
for num in nums:
heapq.heappush(heap, num)
if len(heap) > k:
heapq.heappop(heap)
return heapq.heappop(heap)

lista_numeros = [12, 54, 23, 67, 45, 9, 41, 73]

kth_largest = find_kth_largest(lista_numeros, 3)
print(kth_largest)

Ejercicio 6: Implementar un heap con prioridad personalizada

Implementa un heap que tenga en cuenta una prioridad personalizada para sus elementos. Cada
elemento del heap será una tupla (valor, prioridad) y el heap se ordenará en función de la prioridad.

import heapq

class CustomPriorityHeap:
def __init__(self):
self.heap = []

def insert(self, elemento, prioridad):

heapq.heappush(self.heap, (prioridad, elemento))

def extract_max(self):
_, max_element = heapq.heappop(self.heap)
return max_element

heap_prioridad = CustomPriorityHeap()
heap_prioridad.insert("Tarea 1", 2)

DEPARTAMENTO DE TECNOLOGIA DIGITAL Y GESTION

 Laboratorio de Estructura de Datos y Algoritmos Página | 9

heap_prioridad.insert("Tarea 2", 1)
heap_prioridad.insert("Tarea 3", 3)
max_element = heap_prioridad.extract_max()
print(max_element)

Mostrar una captura de la ejecución

import heapq

class CustomPriorityHeap:
def __init__(self):
self.heap = []

def insert(self, elemento, prioridad):

heapq.heappush(self.heap, (prioridad, elemento))

def extract_max(self):
_, max_element = heapq.heappop(self.heap)
return max_element

heap_prioridad = CustomPriorityHeap()
heap_prioridad.insert("Tarea 1", 2)
heap_prioridad.insert("Tarea 2", 1)
heap_prioridad.insert("Tarea 3", 3)
max_element = heap_prioridad.extract_max()
print(max_element)

Ejercicio 7: Encontrar los elementos comunes en dos listas

Dadas dos listas de números, encuentra los elementos comunes entre ellas utilizando heaps.

def find_common_elements(lista1, lista2):

heap1 = set(lista1)
heap2 = set(lista2)
common_elements = []

for elemento in heap1:

if elemento in heap2:
common_elements.append(elemento)

return common_elements

lista1 = [1, 2, 3, 4, 5]
lista2 = [4, 5, 6, 7, 8]
common_elements = find_common_elements(lista1, lista2)
print(common_elements) # Imprime: [4, 5]

DEPARTAMENTO DE TECNOLOGIA DIGITAL Y GESTION

 Laboratorio de Estructura de Datos y Algoritmos Página | 10

Mostrar una captura de la ejecución

def find_common_elements(lista1, lista2):

heap1 = set(lista1)
heap2 = set(lista2)
common_elements = []

for elemento in heap1:

if elemento in heap2:
common_elements.append(elemento)

return common_elements

lista1 = [1, 2, 3, 4, 5]
lista2 = [4, 5, 6, 7, 8]
common_elements = find_common_elements(lista1, lista2)
print(common_elements)

Ejercicio 8: Encontrar los k elementos más frecuentes

Dada una lista de elementos, encuentra los k elementos más frecuentes utilizando un heap.

def find_k_most_frequent_elements(elements, k):

frequency = {}
for elemento in elements:
frequency[elemento] = frequency.get(elemento, 0) + 1

heap = []
for key, value in frequency.items():
heapq.heappush(heap, (-value, key))

k_most_frequent = []
for _ in range(k):
k_most_frequent.append(heapq.heappop(heap)[1])

return k_most_frequent

elements = [1, 2, 2, 3, 3, 3, 4, 4, 4, 4]
k_most_frequent = find_k_most_frequent_elements(elements, 2)
print(k_most_frequent) # Imprime: [4, 3]

Mostrar una captura de la ejecución

DEPARTAMENTO DE TECNOLOGIA DIGITAL Y GESTION

 Laboratorio de Estructura de Datos y Algoritmos Página | 11

import heapq

def find_k_most_frequent_elements(elements, k):

frequency = {}
for elemento in elements:
frequency[elemento] = frequency.get(elemento, 0) + 1

heap = []
for key, value in frequency.items():
heapq.heappush(heap, (-value, key))

k_most_frequent = []
for _ in range(k):
k_most_frequent.append(heapq.heappop(heap)[1])

return k_most_frequent

elements = [1, 2, 2, 3, 3, 3, 4, 4, 4, 4]
k_most_frequent = find_k_most_frequent_elements(elements, 2)
print(k_most_frequent)

Ejercicio 9: Implementar un heap mínimo con objetos personalizados

Implementa un heap mínimo utilizando objetos personalizados en lugar de valores simples. Considera
una clase Persona con atributos nombre y edad. El heap se ordenará en función de la edad de las
personas.

import heapq

class Persona:
def __init__(self, nombre, edad):
self.nombre = nombre
self.edad = edad

def __lt__(self, other):

return self.edad < other.edad

class HeapMinimo:
def __init__(self):
self.heap = []

def insertar(self, persona):

heapq.heappush(self.heap, persona)

DEPARTAMENTO DE TECNOLOGIA DIGITAL Y GESTION

 Laboratorio de Estructura de Datos y Algoritmos Página | 12

def eliminar_minimo(self):
return heapq.heappop(self.heap)

# Ejemplo de uso
heap_personas = HeapMinimo()
heap_personas.insertar(Persona("Ana", 25))
heap_personas.insertar(Persona("Juan", 30))
heap_personas.insertar(Persona("María", 20))

while len(heap_personas.heap) > 0:

persona = heap_personas.eliminar_minimo()
print(persona.nombre, persona.edad)

La salida será:

María 20
Ana 25
Juan 30

Mostrar una captura de la ejecución

import heapq

class Persona:
def __init__(self, nombre, edad):
self.nombre = nombre
self.edad = edad

def __lt__(self, other):

return self.edad < other.edad

class HeapMinimo:
def __init__(self):
self.heap = []

def insertar(self, persona):

heapq.heappush(self.heap, persona)

def eliminar_minimo(self):
return heapq.heappop(self.heap)

heap_personas = HeapMinimo()
heap_personas.insertar(Persona("Ana", 25))
heap_personas.insertar(Persona("Juan", 30))
heap_personas.insertar(Persona("María", 20))

while len(heap_personas.heap) > 0:

DEPARTAMENTO DE TECNOLOGIA DIGITAL Y GESTION

 Laboratorio de Estructura de Datos y Algoritmos Página | 13

persona = heap_personas.eliminar_minimo()
print(persona.nombre, persona.edad)

Ejercicio 10: Unir y ordenar múltiples listas utilizando un heap

Dadas múltiples listas ordenadas, une y ordena todas las listas en una sola lista utilizando un heap.

def merge_sorted_lists(listas):
heap = []
for i, lista in enumerate(listas):
if lista:
heapq.heappush(heap, (lista[0], i, 0))

merged_list = []
while heap:
val, list_idx, elem_idx = heapq.heappop(heap)
merged_list.append(val)
if elem_idx + 1 < len(listas[list_idx]):
heapq.heappush(heap, (listas[list_idx][elem_idx + 1], list_idx, elem_idx + 1))

return merged_list

lista1 = [1, 4, 7, 10]

lista2 = [2, 5, 6, 8, 11]
lista3 = [3, 9, 12]
listas = [lista1, lista2, lista3]
merged_list = merge_sorted_lists(listas)
print(merged_list) # Imprime: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]

Mostrar una captura de la ejecución

import heapq

def merge_sorted_lists(listas):
heap = []
for i, lista in enumerate(listas):
if lista:
heapq.heappush(heap, (lista[0], i, 0))

merged_list = []
while heap:
val, list_idx, elem_idx = heapq.heappop(heap)
merged_list.append(val)

DEPARTAMENTO DE TECNOLOGIA DIGITAL Y GESTION

 Laboratorio de Estructura de Datos y Algoritmos Página | 14

if elem_idx + 1 < len(listas[list_idx]):

heapq.heappush(heap, (listas[list_idx][elem_idx + 1], list_idx,
elem_idx + 1))

return merged_list

lista1 = [1, 4, 7, 10]

lista2 = [2, 5, 6, 8, 11]
lista3 = [3, 9, 12]
listas = [lista1, lista2, lista3]
merged_list = merge_sorted_lists(listas)
print(merged_list)

Tarea

• Diseña una función que tome dos listas de números ordenadas en forma ascendente y devuelva
la mediana de las dos listas utilizando un heap.
import heapq

def find_median(list1, list2):

merged = heapq.merge(list1, list2)
merged_list = list(merged)
length = len(merged_list)
if length % 2 == 0:
mid = length // 2
median = (merged_list[mid - 1] + merged_list[mid]) / 2
else:
mid = length // 2
median = merged_list[mid]
return median

list1 = [1, 3, 5, 7]
list2 = [2, 4, 6, 8]
median = find_median(list1, list2)
print("La mediana es: ", median)

• Implementa una función que tome una lista de palabras y devuelva las k palabras más
frecuentes utilizando un heap.
import heapq

from collections import Counter

def find_top_k_words(words, k):

word_count = Counter(words)
top_k = heapq.nlargest(k, word_count, key=word_count.get)
return top_k

word_list = ["manzana", "platano", "cereza", "manzana",

"platano", "pera", "cereza", "cereza"]

DEPARTAMENTO DE TECNOLOGIA DIGITAL Y GESTION

 Laboratorio de Estructura de Datos y Algoritmos Página | 15

top_words = find_top_k_words(word_list, 2)
print("Las palabras más frecuentes son:", top_words)

• Crea una función que tome una lista de nombres y sus respectivas edades, y devuelva el nombre
de la persona más joven y de la persona más vieja utilizando un heap mínimo y uno máximo.
import heapq

def find_joven_and_viejo(people):
joven = heapq.nsmallest(1, people, key=lambda x: x[1])
viejo = heapq.nlargest(1, people, key=lambda x: x[1])
return joven[0][0], viejo[0][0]

people_list = [("Javier", 27), ("Jesus", 34), ("Sideral", 19),

("Carrion", 43)]
joven, viejo = find_joven_and_viejo(people_list)
print("Persona más joven:", joven)
print("Persona más vieja:", viejo)

Adjuntar capturas importantes del código

Adjuntar capturas de la prueba del código, así como de su ejecución

Adjuntar el código en un zip, rar, Google drive o git

DEPARTAMENTO DE TECNOLOGIA DIGITAL Y GESTION

 Laboratorio de Estructura de Datos y Algoritmos Página | 16

OBSERVACIONES:
1. Los heaps en Python, implementados a través del módulo heapq, son estructuras de datos
eficientes para mantener y operar con una colección de elementos donde el mínimo (heap
mínimo) o el máximo (heap máximo) está rápidamente accesible.
2. Los heaps en Python son ideales para problemas que requieren la selección de los elementos
más grandes o más pequeños de una colección, como encontrar los k elementos más grandes o
más pequeños.
3. La implementación de heaps en Python proporciona métodos eficientes para realizar
operaciones como la inserción de elementos, extracción del mínimo/máximo, mezcla de heaps y
ordenación en el lugar.
4. Los heaps en Python son útiles en algoritmos de búsqueda, algoritmos de grafos y algoritmos de
compresión.
5. Los heaps en Python tienen una complejidad tiempo para las operaciones como las extracciones
o inserciones del mínimo o máximo.

CONCLUSIONES:
1. Los heaps en Python están representados por listas, donde el elemento mínimo o máximo se
encuentra en la posición 0.
2. En un heap mínimo, cada nodo padre tiene un valor menor o igual que los valores de sus nodos
hijos, mientras que en un heap máximo, cada nodo padre tiene un valor mayor o igual que los
valores de sus nodos hijos.
3. Los heaps en Python son estructuras basadas en árboles binarios completos, lo que permite un
acceso eficiente a los elementos y una rápida inserción y extracción del mínimo/máximo.
4. A diferencia de otras estructuras de datos como los árboles de búsqueda binarios, los heaps en
Python no garantizan un orden total entre los elementos en el mismo nivel del heap. Solo se
garantiza el orden relativo en términos del mínimo/máximo.
5. Los heaps en Python no son tan buenos cuando necesitamos un acceso rapido a los elementos
arbitrarios que estan dentro del HEAP, ya que fueron creados para realizár operaciones de
inserción, extracción y busqueda del mínimo o máximo de una forma correcta.

DEPARTAMENTO DE TECNOLOGIA DIGITAL Y GESTION