Knižničná halda v Pythone a C++

Vo väčšine programovacích jazykov haldu nájdeme v štandardných knižniciach. Netreba teda programovať vlastnú, stačí použiť existujúcu. Napr. v C++ máme dátovú štruktúru priority_queue a v Pythone máme funkcie heappush a heappop v module heapq.

Ukážme si teraz ako s týmito knižničnými haldami pracovať.

Python

V Pythone existujú dve knižnice na prácu s haldou:

  • heapq(import heapq)
  • PriorityQueue (from queue import PriorityQueue)

Práca s heapq

import heapq

halda = [8, 6, 1, 3, 4, 5]
heapq.heapify(halda)
# halda = [1, 3, 5, 6, 4, 8]



heapq.heappush(halda, 9)
heapq.heappush(halda, 15)
heapq.heappush(halda, 0)

while len(halda)!=0:
    heapq.heappop(halda)

Práca s PriorityQueue

from queue import PriorityQueue

q = PriorityQueue()

q.put(4)
q.put(2)
q.put(5)
q.put(1)
q.put(3)

while not q.empty():
    next_item = q.get()
    print(next_item)

Ktorú z knižníci použiť?

Tu je odpoveď pomerne jednoduchá: heapq je rýchlejšia (keďže PriorityQueue je v skutočnosti implementovaná pomocou heapq), a teda väčšinou je lepšie používať heapq.

C++

#include <iostream>
#include <queue>
using namespace std;

int main()
{
    priority_queue<int> pq;
    pq.push(8);
    pq.push(10);
    pq.push(2);

    cout << "size: " << pq.size() << endl;
    cout << "top: " << pq.top() << endl;

    while (!pq.empty()) {
        cout << "pop() : ";
        pq.pop();
    }
}
Späť Ďalej