Kopiec

Z RNO-Wiki
Wersja Rno (dyskusja | edycje) z dnia 13:57, 29 lis 2007
(różn.) ← poprzednia wersja | przejdź do aktualnej wersji (różn.) | następna wersja → (różn.)

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++

template <typename T>
struct Heap
{
       int n;
       vector< T > tab;

       Heap () { n=0; }
       Heap (int size)  { tab.resize(size+1); n=0; }
       int  max()   { return tab[1]; }
       bool empty() { return n==0; }

       bool insert(T x)
       {
            n++;
            if (n>=tab.size()) tab.resize(2*n);
            tab[n]=x;
            sift_up(n);
       }         

       bool delMax()
       {
            if (n<1) return false;
            
            tab[1]=tab[n]; n--;
            sift_down(1);
            return true;
       }

	void sift_up(int x)
	{
		int p; T mem = tab[x];
		while (x>1)
		{
			p=x/2;
			if (mem<tab[p]) break;
			tab[x]=tab[p];
			x=p;
		}
		tab[x]=mem;
	}

	void sift_down (int x)
	{
		int s=2*x; T mem=tab[x];
		while(s<=n)
		{
			if (s+1<=n && tab[s]<tab[s+1]) s++;
			if (mem<tab[s])
			{
				tab[x]=tab[s];
				x=s;
				s=2*x;
			}
			else break;
		}
		tab[x]=mem;
	}
	
	void write ()
	{
		for (int i=1;i<=n;i++) printf ("%d) %d\n", i, tab[i]);
		printf ("\n");
	}       
	
	void build()
	{
		int s = n;
		for (s=n/2; s>=1; s--) sift_down(s);
	}
};

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;
}

Rafał Nowak 14:49, 29 lis 2007 (CET)


Kopce w STL-u

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

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 [1].

Osobiste