Heapsort

[dranaxum]

Sursa: http://hackpedia.info/viewtopic.php?f=121&t=5311

Unul dintre cele mai rapide si stabile algoritme de sortare. O(N * log N) chiar si pentru cazurile defavorabile, fata de QSort care ajunge la O(N^2) pentru astfel de cazuri.

Informatii despre HEAP (arbore binar complet) aici: http://en.wikipedia.org/wiki/Heap_(data_structure)

O solutie in C:

#include<stdio.h>

FILE *fin=freopen("heap.in","r",stdin);
FILE *fout=freopen("heap.out","w",stdout);


int h[100],n;//h reprezinta vectorul in care stocam heap-ul

void corecteazaheap(int i)
{
	while(i>=2 && h[i]>h[i/2])
	{
                //interschimbam nodul parinte cu nodul curent pentru a corecta arborele
		h[i]=h[i]+h[i/2];
		h[i/2]=h[i]-h[i/2];
		h[i]=h[i]-h[i/2];
		i/=2;
	}
}

void extragere(int i)
{
        //elementul 1 va fi cel mai mare element din vector pe [1,i] => il punem pe pozitia i, si decrementam i-ul
	h[1]+=h[i];
	h[i]=h[1]-h[i];
	h[1]=h[1]-h[i];
	i--;
	int j=1;
        //corectam noul heap
	while(2*j<=i && (h[j]<h[j*2] || h[j]<h[j*2+1]))
	{
		int max=h[j*2];
		int poz=j*2;
		if(max<h[j*2+1] && 2*j+1<=i)
		{
			max=h[j*2+1];
			poz=j*2+1;
		}
		if(h[j]<h[poz]){
		h[j]+=h[poz];
		h[poz]=h[j]-h[poz];
		h[j]=h[j]-h[poz];}

		j=poz;
	}
}

void citire()
{
	scanf("%d",&n);
	int i;
	for(i=1;i<=n;i++)
	{
	scanf("%d",&h[i]);
	corecteazaheap(i);//inseram elementele in heap
	}
	fclose(fin);
}

void rezolva()
{
	for(int i=n;i>=2;i--)
	{
		extragere(i);
	}
}

void afiseaza()
{
	for(int i=1;i<=n;i++)
	{
	printf("%d ",h[i]);
	}
	fclose(fout);
}

int main()
{
  citire();
  rezolva();
  afiseaza();
  return 0;
}

O solutie in C++ folosind libraria STL:

#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

ifstream fin("heap.in");
ofstream fout("heap.out");

vector<int> h;//vectorul care va stoca heap-ul

void citire()
{
    int n;
    fin>>n;
    for(int i=1;i<=n;i++)
    {
        int x;
        fin>>x;
        //adaugam elemente in vector
        h.push_back(x);
    }
    fin.close();
}

void rezolva()
{
    //cream heapul
    make_heap(h.begin(),h.end());
    //sortam heapul
    sort_heap(h.begin(),h.end());
}

void afiseaza()
{
    for(int i=0;i<h.size();i++)
        fout<<h[i]<<" ";
    fout.close();
}

int main () {
  citire();
  rezolva();
  afiseaza();  
  return 0;
}