Kopiec

Z RNO-Wiki

Kopiec to struktura danych pozwalająca realizować następujące operacje

  1. insert(x) - wstaw do zbioru element 'x'
  2. max() - podaj wartość elementu maksymalnego w zbiorze
  3. delMax() - usuń ze zbioru element maksymalny

Złożoność czasowa powyższych operacji jest następująca (przy założeniu, że aktualnie w kopcu jest 'n' elementów):

  1. insert(x) - O(log(n)) - czas logarytmiczny
  2. max() - O(1) - czas stały
  3. delMax() - O(log(n)) - czas logarytmiczny

Implementacja kopca w C++

#include<vector>
template<class key>
class Heap {
private:
	std::vector<key> tab;
 
	void up(unsigned int k) { // podnoszenie elementu tab[k] w górę
		key x=tab[k];
		unsigned int p=k>>1;
		while(p)
			if ( tab[p]<x ) {
				tab[k] = tab[p];
				k=p; p=k>>1;
			}
			else break;
		tab[k] = x;
	}
 
	void down(unsigned int k) { // opuszczanie elementu tab[k] w dół
		key x=tab[k];
		unsigned int son=k<<1;
		while ( son < tab.size() ) {
			static unsigned int right = son+1;
			if ( right<tab.size() && tab[son]<tab[right] ) son = right;
			if ( x<tab[son] ) {
				tab[k] = tab[son];
				k = son; son <<= 1;
			}
			else break;
		}
		tab[k] = x;
	}
 
public:
	// Domyślny konstruktor
	// wstawiamy jeden element do wektora tab (marnujemy tab[0])
	Heap() : tab(1) {};
	void push_back(key x) { tab.push_back(x); }
	void push(key x)    { push_back(x); up( tab.size()-1 ); }
	void pop()          { tab[1] = tab.back(); tab.pop_back(); down( 1 ); }
	bool empty()        { return tab.size()==1; }
	key  top()          { return tab[1]; }
	void build()        { for(unsigned int k=(tab.size()-1)/2; k; k--) down(k);}
	unsigned int size() { return tab.size()-1; }
	void decrease(unsigned int pos, key value) { tab[pos]=value; down(pos); }
	void increase(unsigned int pos, key value) { tab[pos]=value; up(pos); }
};

Przykład użycia

Powyższej struktury należy używać następująco:

#include<iostream>
using namespace std;
int main(void)
{
	int x, n;
	Heap<int> H;
	cin >> n;
 
	// operacja H.push_back(x) wstawia element x do vectora i nie dba o porządek kopcowy
	for (int i=1; i<=n; i++) { cin >> x; H.push_back(x); }  // po kolei wczytujemy liczby do zbioru
 
	H.build(); // dopiero teraz tworzymy porządek kopcowy; złożoność = O(n), czyli liniowa
	//sort(H.tab.begin()+1, H.tab.end()); // można było zrobić to tak, ale to działa w czasie O(n log(n))
 
	H.push(10);
	cout << H.top() << endl;
	H.pop();
	cout << H.top() << endl;
	H.pop();
	cout << H.top() << endl;
	H.push(100);
	cout << H.top() << endl;
 
	while (!H.empty()) H.pop();
}

Kopce w STL-u

W bibliotece STL (Standard Tamplate Library) można znaleźć implementację kopca, jako priority_queue ([1]).

Poniżej znajduje się przykład jej uzycia:

#include<queue>
using namespace stdl
int main()
{
	priority_queue<int> Q;
	Q.push(1); 
	Q.push(4); 
	Q.push(2); 
	Q.push(8); 
	Q.push(5); 
	Q.push(7); 
 
	Q.pop();   
	Q.top();
	Q.empty();
}

Należy pamiętać, że domyślnie w priority_queue znajduje się maksimum. Przeczytaj artykuł na moim blog-u, aby dowiedzieć się jako zrobić aby było tam minimum [2].

Osobiste