Kopiec

Z RNO-Wiki
(Różnice między wersjami)
m (Kopce w STL-u)
m
Linia 11: Linia 11:
  
 
== Implementacja kopca w C++ ==
 
== Implementacja kopca w C++ ==
<table width="100%">
 
<tr>
 
<td valign="top">
 
 
<source lang="cpp">
 
<source lang="cpp">
template <typename T>
+
#include<vector>
struct Heap
+
template<class key>
{
+
class Heap {
      int n;
+
private:
      vector< T > tab;
+
std::vector<key> tab;
  
      Heap () { n=0; }
+
void up(unsigned int k) { // podnoszenie elementu tab[k] w górę
      Heap (int size) { tab.resize(size+1); n=0; }
+
key x=tab[k];
      int  max()  { return tab[1]; }
+
unsigned int p=k>>1;
      bool empty() { return n==0; }
+
while(p)
 
+
if ( tab[p]<x ) {
      bool insert(T x)
+
tab[k] = tab[p];
      {
+
k=p; p=k>>1;
            n++;
+
}
            if (n>=tab.size()) tab.resize(2*n);
+
else break;
            tab[n]=x;
+
tab[k] = 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)
+
void down(unsigned int k) { // opuszczanie elementu tab[k] w dół
{
+
key x=tab[k];
int s=2*x; T mem=tab[x];
+
unsigned int son=k<<1;
while(s<=n)
+
while ( son < tab.size() ) {
{
+
static unsigned int right = son+1;
if (s+1<=n && tab[s]<tab[s+1]) s++;
+
if ( right<tab.size() && tab[son]<tab[right] ) son = right;
if (mem<tab[s])
+
if ( x<tab[son] ) {
{
+
tab[k] = tab[son];
tab[x]=tab[s];
+
k = son; son <<= 1;
x=s;
+
s=2*x;
+
 
}
 
}
 
else break;
 
else break;
 
}
 
}
tab[x]=mem;
+
tab[k] = x;
}
+
+
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);
+
 
}
 
}
 +
 +
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); }
 
};
 
};
 
</source>
 
</source>
</td>
 
<td width="140" align="center">
 
<adsense
 
adclient="pub-2033664350513674"
 
adslot="5958906648"
 
adwidth="120"
 
adheight="600"
 
/>
 
</td>
 
</tr>
 
</table>
 
  
 
=== Przykład użycia ===
 
=== Przykład użycia ===

Wersja z 12:02, 20 gru 2012

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

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 ([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