algorytm.org

Implementacja w C/C++

Praca
Interesuje Cię praca przy weryfikacji oprogramowania do samolotów?
Sprawdź to!
Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Kopiec (Stóg) - Implementacja w C/C++
Ocena użytkownikóww: *****  / 12
SłabyŚwietny
Nadesłany przez Mateusz Lewko, 13 stycznia 2013 15:45
Kod przedstawiony poniżej przedstawia główną część rozwiązania problemu.
Pobierz pełne rozwiązanie.

Jeżeli nie odpowiada Ci sposób formatowania kodu przez autora skorzystaj z pretty printer'a i dostosuj go automatycznie do siebie.

kopiec.cpp:
//Kopiec
//www.algorytm.org

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <math.h>
using namespace std;

int Heap[50001], pos = 0;

//zwraca indeks rodzica dla podanego indeksu wierzcholka
int Parent(int v)
{
	return v / 2;
}

//zwraca indeks lewego dziecka dla podanego indeksu wierzcholka
int LeftSon(int v)
{
	return 2 * v;
}

//zwraca indeks prawego dziecka dla podanego indeksu wierzcholka
int RightSon(int v)
{
	return 2 * v + 1;
}

//wypisuje wierzcholek kopca, o ile istnieje
void Top (void)
{
	if (pos != 0)
		cout << Heap[1] << "\n";
}

//wstawia podana wartosc do kopca	
void Insert (int x)
{
	Heap[pos+1] = x; //wstaw na koniec
	pos++;           //zwieksz liczbe elementow kopca
	int v = pos;  
	while (v != 1 and Heap[Parent(v)] < Heap[v]) //przywroc wlasciwosc kopca
	{
		swap (Heap[Parent(v)], Heap[v]);
		v=Parent(v);
	}
}

//Usuwa wierzcholek kopca
void Remove()
{
	if (pos==0)      //jezeli kopiec jest pusty zakoncz bez zadnej akcji
		return;

	Heap[1]=Heap[pos]; //wstaw ostatni element do wierzcholka
	pos--;             //zmniejsz liczbe elementow kopca
	
	int v = 1;
	while(true) //przywroc wlasciwosc kopca
	{
		if (LeftSon(v) > pos)
			break;
		int a = Heap[LeftSon(v)];
		if (RightSon(v) > pos)
		{
			if (Heap[v] >= Heap[LeftSon(v)])
				break;
			swap (Heap[v], Heap[LeftSon(v)]);
			v=LeftSon(v);
		}
		else if (Heap[LeftSon(v)] > Heap[RightSon(v)])
          	{
			if (Heap[v] >= Heap[LeftSon(v)])
				break;
			swap (Heap[v], Heap[LeftSon(v)]);
			v=LeftSon(v);
		}
		else
		{
			if (Heap[v] >= Heap[RightSon(v)])
				break;
			swap (Heap[v], Heap[RightSon(v)]);
			v=RightSon(v);
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(0);
	int n;
	cin >> n; // ilosc operacji na kopcu

	while(n--)
	{
		string s;
		cin >> s;

		if (s=="push")
		{
			int x;
			cin >> x;
			Insert(x);
		}

		if (s=="pop")
			Remove();

		if (s=="top")
			Top();
	}
	cout << "all done";
}
Komentarze
photo
-7 # Żbiku 2015-01-11 14:14
Funkcje od rodzica i dzieci są źle napisane - lewy syn to (2*rodzic) + 1, prawy syn to (rodzic + 1) * 2, rodzic to (wierzchołek - 1) / 2. Pozdrawiam. :) :)
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
+3 # Tomasz Lubiński 2015-09-28 08:47
Funkcje są poprawne, zwróć uwagę, że autor zastosował numerację od 1. Czyli:
- indeks zerowy jest nieużywany,
- indeks 1 to korzeń,
- indeksy 2 i 3 to dzieci korzenia,
- indeksy 4 i 5 to dzieci 2,
- indeksy 6 i 7 to dzieci 3,
- itd...

Zatem przy podanych założeniach funkcje są OK.
Odpowiedz | Odpowiedz z cytatem | Cytować
Dodaj komentarz