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:

int main(void)
{
	Heap<int> H;
 
	cin >> H.n;                                  // wczytujemy rozmiar kopca
	H.tab.resize(H.n+1);
	for (int i=1; i<=H.n; i++) cin >> H.tab[i];  // po kolei wczytujemy liczby do zbioru
 
	H.build(); // tworzymy porządek kopcowy w czasie O(n), czyli liniowym
//	sort(H.tab+1, H.tab+H.n+1); // można byłoby zrobić tak, ale to działa w czasie O(n log(n))
 
	H.insert(10);
	cout << H.max() << endl;
	H.delMax();
	cout << H.max() << endl;
	H.delMax();
	cout << H.max() << endl;
	H.insert(100);
	cout << H.max() << endl;
}

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); // insert(1)
	Q.push(4); // insert(4)
	Q.push(2); // insert(2)
	Q.push(8); // insert(8)
	Q.push(5); // insert(5)
	Q.push(7); // insert(7)
 
	Q.pop();   // delMax()
	Q.top();   // max()
	Q.empty(); // 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