kupac
Kiejtés
- IPA: [ ˈkupɒt͡s]
Főnév
kupac
- (informatika) A kupac (más néven halom) egy speciális fa alapú adatszerkezet, amely eleget tesz a kupac tulajdonságnak, azaz ha a B csúcs fia az A csúcsnak, akkor kulcs(A) ≥ kulcs(B) - és ebben az esetben a kupacot max-kupacnak (vagy maximum-kupacnak) nevezzük. Az összehasonlítás megfordításával min-kupacot (azaz minimum-kupacot) kapunk, melyben minden A csúcsból leszármazó B csúcshoz kulcs(B) ≥ kulcs(A). A kupac egy maximálisan hatékony implementációja a prioritási sor adatszerkezetnek.
Íme egy egyszerű kupac (heap) implementáció Pythonban a beépített heapq modul használatával, valamint egy saját megvalósítás is, ha mélyebb megértést szeretnél.
1. Python beépített heapq modul
A Python heapq modulja egy min-heap megvalósítást biztosít.
import heapq
# Kezdeti üres kupac
heap = []
# Elemek beszúrása a kupacba
heapq.heappush(heap, 10)
heapq.heappush(heap, 1)
heapq.heappush(heap, 5)
# Kupac tartalma
print("Heap tartalma:", heap) # Min-heap, nem feltétlen rendezett lista, de a legkisebb az első.
# Legkisebb elem kivétele
min_elem = heapq.heappop(heap)
print("Kivett legkisebb elem:", min_elem)
# Csak a legkisebb elem megnézése
peek = heap[0]
print("Legkisebb elem (megnézve):", peek)
# Tömbből kupac készítése
array = [10, 1, 5, 7, 2]
heapq.heapify(array)
print("Kupacosított tömb:", array)
2. Max-Heap megvalósítása a heapq modul segítségével
Mivel a heapq csak min-heap-et támogat, egy egyszerű trükk segítségével megvalósíthatunk egy max-heap-et: az elemeket negatív előjellel tároljuk.
import heapq
# Kezdeti üres kupac
max_heap = []
# Elemek beszúrása (negatív előjellel)
heapq.heappush(max_heap, -10)
heapq.heappush(max_heap, -1)
heapq.heappush(max_heap, -5)
# Kupac tartalma (negatív számok, de logikailag max-heap)
print("Max-heap tartalma (negatív):", max_heap)
# Legnagyobb elem kivétele
max_elem = -heapq.heappop(max_heap)
print("Kivett legnagyobb elem:", max_elem)
3. Saját bináris heap implementáció
Ha szeretnél saját min-heap-et megvalósítani, íme egy egyszerű példa:
class MinHeap:
def __init__(self):
self.heap = []
def push(self, val):
"""Elem beszúrása a kupacba"""
self.heap.append(val)
self._bubble_up(len(self.heap) - 1)
def pop(self):
"""Legkisebb elem kivétele a kupacból"""
if len(self.heap) == 0:
raise IndexError("Üres a kupac!")
if len(self.heap) == 1:
return self.heap.pop()
min_val = self.heap[0]
self.heap[0] = self.heap.pop()
self._bubble_down(0)
return min_val
def peek(self):
"""Legkisebb elem megtekintése"""
if not self.heap:
raise IndexError("Üres a kupac!")
return self.heap[0]
def _bubble_up(self, index):
"""Buborékolás felfelé"""
parent = (index - 1) // 2
while index > 0 and self.heap[index] < self.heap[parent]:
self.heap[index], self.heap[parent] = self.heap[parent], self.heap[index]
index = parent
parent = (index - 1) // 2
def _bubble_down(self, index):
"""Buborékolás lefelé"""
child = 2 * index + 1
while child < len(self.heap):
# Kiválasztjuk a kisebbik gyermeket
if child + 1 < len(self.heap) and self.heap[child + 1] < self.heap[child]:
child += 1
if self.heap[index] <= self.heap[child]:
break
self.heap[index], self.heap[child] = self.heap[child], self.heap[index]
index = child
child = 2 * index + 1
# Használat
heap = MinHeap()
heap.push(10)
heap.push(1)
heap.push(5)
print("Kupac csúcsa:", heap.peek()) # 1
print("Kivett legkisebb:", heap.pop()) # 1
print("Kivett legkisebb:", heap.pop()) # 5
Ezekkel a megoldásokkal könnyen kezelhetsz kupac alapú prioritási sorokat Pythonban!
Fordítások
Főnév
kupac hn (cirill írás купац)