Sortari

Heap Sort

Posted by Feroviarul on

Aspecte teoretice:

Un ”Heap”, numit uneori ansamblu sau movilă este un tablou de elemente H[1..n] care are proprietatea ca pentru fiecare element H[i] cu 1<=i<=[n/2] sunt adevărate inegalitățile: H[i]>=H[2i] si H[i]>=H[2i+1] (în cazul în care 2i+1<=n. O astfel de structură poate fi vizualizată sub forma unui arbore binar aproape complet (arbore în care fiecare nod are doi fii, iar fiecare nivel cu excepția ultimului este complet). fii unui nod aflat pe poziția i în tablou se află pe pozițiile 2i (fiul stâng) respectiv 2i+1 (fiu drept). În baza aceleiași proprietăți părintele nodului de pe poziția i în tablou se află pe poziția [i/2].
Aceste structuri de date sunt utile atât pentru sortarea eficientă a unui tablou cât și pentru implementarea cozilor de priorități. În această secțiune structura de tip “heap” este folosită doar pentru implementarea unei metode de sortare.
Procesul propriu zis de sortare constă în doua etape principale:

  • Construirea, pornind de la tabloul inițial al unui heap. Procesul de construire se bazează pe utilizarea algoritmului reHeap pentru fiecare element din prima jumătate a tabloului începând cu elementul de pe poziția [n/2]
  • Eliminarea succesivă din heap a nodului rădăcină și plasarea acestuia la sfârșitul tabloului corespunzător heap-ului. La fiecare etapă dimensiunea heap-ului scade cu un element iar subtabloul ordonat de la sfârșitul zonei corespunzătoare tabloului inițial crește cu un element.

Analiza complexității:

Întrucât algoritmul heapSort apelează de n-1 ori algoritmul reHeap care are ordinul de complexitate O(log n) iar cum algoritmul de construire are ordinul O(nlog n) rezultă ca heapSort are de asemenea ordinul O(nlog n).

Exemplu Pas cu Pas:

Heap Sort Exemplu

Implementare:

Logo_C_Sharp
Cod Sursa C#
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
 
namespace HeapSortCS
{
    class Program
    {
        static void heapify(int[] v, int root, int bottom)
        {
            int maxChild, aux;
            bool done;
            done = false;
            while ((root * 2 <= bottom) && (!done))
            {
                if (root * 2 == bottom)
                    maxChild = root * 2;
                else
                    if (v[root * 2] > v[root * 2 + 1])
                        maxChild = root * 2;
                    else
                        maxChild = root * 2 + 1;
                if (v[root] < v[maxChild])
                {
                    aux = v[root];
                    v[root] = v[maxChild];
                    v[maxChild] = aux;
                    root = maxChild;
                }
                else
                    done = true;
            }
        }
 
        static void HeapSort(int[] v, int len)
        {
            int i, aux;
            for (i = (len / 2) - 1; i >= 0; i--)
                heapify(v, i, len);
            for (i = len - 1; i >= 1; i--)
            {
                aux = v[0];
                v[0] = v[i];
                v[i] = aux;
                heapify(v, 0, i - 1);
            }
        }
 
        static void Main(string[] args)
        {
            int[] v = new int[20];
            int i;
            int len;
            Console.Write("Dati numarul de elemente din vector: ");
            len = Convert.ToInt32(Console.ReadLine());
            for (i = 0; i < len; i++)
            {
                Console.Write("v[" + i + "]=");
                v[i]=Convert.ToInt32(Console.ReadLine());
            }
            HeapSort(v, len);
            for (i = 0; i < len; i++)
                Console.Write(v[i] + " ");
            Console.ReadLine();
        }
    }
}
Logo_VB
Cod Sursa VB
Module Module1
 
    Private Sub heapify(v As Integer(), root As Integer, bottom As Integer)
        Dim maxChild As Integer, aux As Integer
        Dim done As Boolean
        done = False
        While (root * 2 <= bottom) AndAlso (Not done)
            If root * 2 = bottom Then
                maxChild = root * 2
            ElseIf v(root * 2) > v(root * 2 + 1) Then
                maxChild = root * 2
            Else
                maxChild = root * 2 + 1
            End If
            If v(root) < v(maxChild) Then
                aux = v(root)
                v(root) = v(maxChild)
                v(maxChild) = aux
                root = maxChild
            Else
                done = True
            End If
        End While
    End Sub
 
    Private Sub HeapSort(v As Integer(), len As Integer)
        Dim i As Integer, aux As Integer
        For i = (len / 2) - 1 To 0 Step -1
            heapify(v, i, len)
        Next
        For i = len - 1 To 1 Step -1
            aux = v(0)
            v(0) = v(i)
            v(i) = aux
            heapify(v, 0, i - 1)
        Next
    End Sub
 
    Sub Main(args As String())
        Dim v As Integer() = New Integer(19) {}
        Dim i As Integer
        Dim len As Integer
        Console.Write("Dati numarul de elemente din vector: ")
        len = Convert.ToInt32(Console.ReadLine())
        For i = 0 To len - 1
            Console.Write("v[" & i & "]=")
            v(i) = Convert.ToInt32(Console.ReadLine())
        Next
        HeapSort(v, len)
        For i = 0 To len - 1
            Console.Write(v(i) & " ")
        Next
        Console.ReadLine()
    End Sub
 
 
End Module
Visual_C++_Icon
Cod Sursa C++
// HeapSortCPP.cpp : Defines the entry point for the console application.
//
 
#include "stdafx.h"
#include <iostream>
 
using namespace std;
 
int v[100];
 
void heapify(int v[], int root, int bottom)
{
	int done, maxChild, aux;
	done=0;
	while ((root*2 <= bottom) && (!done))
	{
		if(root*2 == bottom)
			maxChild = root *2;
		else
			if(v[root*2] > v[root*2+1])
				maxChild=root*2;
			else
				maxChild=root*2+1;
		if(v[root]<v[maxChild])
		{
			aux=v[root];
			v[root]=v[maxChild];
			v[maxChild]=aux;
			root=maxChild;
		}
		else
			done=1;
	}
}
 
void HeapSort(int v[], int len)
{
	int i,aux;
	for (i=(len/2)-1; i>=0; i--)
		heapify(v,i,len);
	for (i=len-1; i>=1; i--)
	{
		aux=v[0];
		v[0]=v[i];
		v[i]=aux;
		heapify(v,0,i-1);
	}
}
 
int main(void)
{
	int i;
	int len;
	cout<<"Dati numarul de elemente din vector: ";
	cin>>len;
	for (i=0; i<len; i++)
	{
		cout<<"v["<<i<<"]=";
		cin>>v[i];
	}
	HeapSort(v, len);
	for (i=0; i<len; i++)
		cout<<v[i]<<" ";
	system("pause");
}
phplogo
Cod Sursa PHP
<?php

class Node
{
    private $_i; 
    
    public function __construct($key)
    {
        $this->_i = $key;
    }
    
    public function getKey()
    {
        return $this->_i;
    }
}
 
class Heap
{
    private $heap_Array;
    private $_current_Size;
    
    public function __construct()
    {
        $heap_Array = array();
        $this->_current_Size = 0;
    }
    
    // Remove item with max key <p></p>
    public function remove()
    {
        $root = $this->heap_Array[0];
        // put last element into root
        $this->heap_Array[0] = $this->heap_Array[--$this->_current_Size];
        $this->bubbleDown(0); 
        return $root; 
    }
    
    // Shift process
    public function bubbleDown($index)
    {
        $larger_Child = null;
        $top = $this->heap_Array[$index]; // save root
        while ($index < (int)($this->_current_Size/2)) { // not on bottom row
            $leftChild = 2 * $index + 1;
            $rightChild = $leftChild + 1;
            
            // find larger child
            if ($rightChild < $this->_current_Size 
            && $this->heap_Array[$leftChild] < $this->heap_Array[$rightChild]) // right child exists?
            {
                $larger_Child = $rightChild;
            } else {
                $larger_Child = $leftChild;
            }
            
            if ($top->getKey() >= $this->heap_Array[$larger_Child]->getKey()) {
                break;
            }
            
            // shift child up
            $this->heap_Array[$index] = $this->heap_Array[$larger_Child]; 
            $index = $larger_Child; // go down
        }
        
        $this->heap_Array[$index] = $top; // root to index
    }
    
    public function insertAt($index, Node $newNode)
    {
        $this->heap_Array[$index] = $newNode;
    }
    
    public function incrementSize()
    {
        $this->_current_Size++;
    }
    
    public function getSize()
    {
        return $this->_current_Size;
    }
    
    public function asArray()
    {
        $arr = array();
        for ($j = 0; $j < sizeof($this->heap_Array); $j++) {
            $arr[] = $this->heap_Array[$j]->getKey();
        }
        
        return $arr;
    }
}
 
function heapsort(Heap $Heap)
{ 
    $size = $Heap->getSize();
    // "sift" all nodes, except lowest level as it has no children
    for ($j = (int)($size/2) - 1; $j >= 0; $j--) 
    {
        $Heap->bubbleDown($j);
    }
    // sort the heap
    for ($j = $size-1; $j >= 0; $j--) { 
        $BiggestNode = $Heap->remove();
        // use same nodes array for sorted elements
        $Heap->insertAt($j, $BiggestNode);
    }
    
    return $Heap->asArray(); 
}
 
$arr = array(3, 0, 2, 5, -1, 4, 1);
echo "Vectorul original : ";
echo implode(', ',$arr ); 
$Heap = new Heap();
foreach ($arr as $key => $val) {
    $Node = new Node($val);
    $Heap->insertAt($key, $Node);
    $Heap->incrementSize();
}
$result = heapsort($Heap);
echo "\nVectorul sortat : ";
echo implode(', ',$result)."\n";
sleep(10);
?>
Java-Logo
Cod Sursa JAVA


//Complexitate: Nefavorabil: O(n*log n); Mediu: O(n*log n); Favorabil: O(n*log n)class HeapSortJAVA
{
  public static void heapify(int v[], int root, int bottom)
        {
            int maxChild, aux;
            boolean done;
            done = false;
            while ((root * 2 <= bottom) && (!done))
            {
                if (root * 2 == bottom)
                    maxChild = root * 2;
                else
                    if (v[root * 2] > v[root * 2 + 1])
                        maxChild = root * 2;
                    else
                        maxChild = root * 2 + 1;
                if (v[root] < v[maxChild])
                {
                    aux = v[root];
                    v[root] = v[maxChild];
                    v[maxChild] = aux;
                    root = maxChild;
                }
                else
                    done = true;
            }
        }        public static void HeapSort(int v[], int len)
        {
            int i, aux;
            for (i = (len / 2) – 1; i >= 0; i–)
                heapify(v, i, len);
            for (i = len – 1; i >= 1; i–)
            {
                aux = v[0];
                v[0] = v[i];
                v[i] = aux;
                heapify(v, 0, i – 1);
            }
        }    

public static void main(String args[])
    {
      int a[]={7,4,5,0,3,1,8,9,2,6};
      int i;

      HeapSort(a,10);
      for (i=0;i<10;i++)
      System.out.println(a[i]+” “);
    }
}

 

Rezultat:

quicksortrezultat

Leave a comment