Heapsort
From Algorithm wiki
 Related content:
|
Contents |
[edit] Pseudocode
Heap-Sort (A)
n <-- length[A]
for j <-- n/2 downto 1 do
Heapfy(A,j,n)
for i <-- n downto 2 do
t <-- A[i], A[i] <-- A[1], A[1] <-- t
Heapfy(A,1,i-1)
Heapfy (A,j,n)
k <-- j
if 2j+1 <= n and A[2j+1] > A[k] then k <-- 2j+1
if 2j <= n and A[2j] > A[k] then k <-- 2j
if k <= j then
t <-- A[j], A[j] <-- A[k], A[k] <-- t
Heapfy(A,k,n)
[edit] C Code
This code will sort an integer array using Heap Sort algorithm
#include<stdio.h>
#include<conio.h>
#include<math.h>
void swap(int *p, int *q);
void HEAPSORT(int heap[100], int n);
int BUILD_HEAP(int heap[100],int n);
void HEAPIFY(int heap[100], int i, int heap_size);
int PARENT(int i);
int LEFT(int i);
int RIGHT(int i);
//int heap_size;
void main()
{
int i,j,n;
int heap[110];
while(1)
{
printf("Enter the number of element (0 to exit): ");
scanf("%d",&n);
if(n==0)
break;
for(i=1;i<=n;++i)
scanf("%d",&heap[i]);
HEAPSORT(heap,n);
printf("The sorted List is:\n");
for(i=1;i<=n;++i)
printf("%d ",heap[i]);
}
}
void HEAPSORT(int heap[100], int n)
{
int i,heap_size;
heap_size = BUILD_HEAP(heap,n);
for(i=n;i>=2;--i)
{
swap(&heap[1],&heap[i]);
--heap_size;
HEAPIFY(heap,1,heap_size);
}
}
void swap(int *p, int *q)
{
int t;
t=*p;
*p=*q;
*q=t;
}
int BUILD_HEAP(int heap[100],int n)
{
int i, heap_size;
heap_size = n;
for(i=floor(n/2);i>=1;--i)
HEAPIFY(heap,i,heap_size);
return heap_size;
}
void HEAPIFY(int heap[100], int i, int heap_size)
{
int l,r,largest;
l = LEFT(i);
r = RIGHT(i);
if(l <= heap_size && heap[l] > heap[i])
largest = l;
else
largest = i;
if(r <= heap_size && heap[r] > heap[largest])
largest = r;
if(largest != i)
{
swap(&heap[i],&heap[largest]);
HEAPIFY(heap,largest,heap_size);
}
}
int PARENT(int i)
{return (i/2);}
int LEFT(int i)
{return (2*i);}
int RIGHT(int i)
{return ((2*i)+1);}
- another c code
/* Heapsort based on ideas of J.W.Williams/R.W.Floyd/S.Carlsson */
#define data_i_LESS_THAN_(other) (data[i] < other)
#define MOVE_i_TO_free { data[free]=data[i]; free=i; }
void sift_in(unsigned count, SORTTYPE *data, unsigned free_in,
SORTTYPE next)
{
unsigned i;
unsigned free = free_in;
// sift down the free node
for (i=2*free;i<count;i+=i)
{ if (data_i_LESS_THAN_(data[i+1])) i++;
MOVE_i_TO_free
}
// special case in sift down if the last inner node has only 1 child
if (i==count)
MOVE_i_TO_free
// sift up the new item next
while( ((i=free/2)>=free_in) && data_i_LESS_THAN_(next))
MOVE_i_TO_free
data[free] = next;
}
void heapsort(unsigned count, SORTTYPE *data)
{
unsigned j;
if (count <= 1) return;
data-=1; // map addresses to indices 1 til count
// build the heap structure
for(j=count / 2; j>=1; j--) {
SORTTYPE next = data[j];
sift_in(count, data, j, next);
}
// extract extremal element and sift_in next element
for(j= count - 1; j>=1; j--) {
SORTTYPE next = data[j + 1];
data[j + 1] = data[1]; // extract extremal element from the heap
sift_in(j, data, 1, next);
}
}
[edit] C++ Code
template <typename Type>
void HeapSort(Type *pF, Type *pL)
{
for (int k=(pL-pF)/2; k>=1; k--) {
Heapify(pF, pL, k);
}
for (; pF < --pL;) {
iter_swap(pF, pL);
Heapify(pF, pL, 1);
}
}
template <typename Type> inline
void Heapify(Type *pF, Type *pL, int k)
{
Type v = *(pF + k-1);
int nChild;
while (k <= (pL-pF)/2) {
nChild = k<<1;
if ((nChild < pL-pF) && *(pF + nChild-1) < *(pF + nChild)) {
nChild++;
}
if (v >= *(pF + nChild-1)) {
break;
}
*(pF + k-1) = *(pF + nChild-1);
k = nChild;
}
*(pF + k-1) = v;
}
[edit] PHP Code
This section needs your Code! ¬¬
[edit] C# Code
/// <summary>
/// min heap sort
/// </summary>
/// <param name="dblArray"></param>
/// <param name="StartIndex"></param>
/// <returns></returns>
private static void HeapSort(ref double[] dblArray )
{
for(int i = dblArray.Length -1 ; i >= 0; i--)
{
if(2*i+1<dblArray.Length)
{
int MinChildrenIndex = 2*i+1 ;
if(2*i+2 < dblArray.Length )
{
if(dblArray[2*i+1]>dblArray[2*i+2])
MinChildrenIndex = 2*i+2;
}
if(dblArray[i] > dblArray[MinChildrenIndex])
{
ExchageValue(ref dblArray[i],ref dblArray[MinChildrenIndex]);
NodeSort(ref dblArray ,MinChildrenIndex);
}
}
}
}
/// <summary>
/// node sort
/// </summary>
/// <param name="dblArray"></param>
/// <param name="StartIndex"></param>
private static void NodeSort(ref double[] dblArray,int StartIndex)
{
while(2*StartIndex+1 < dblArray.Length)
{
int MinChildrenIndex = 2*StartIndex+1 ;
if(2*StartIndex+2 < dblArray.Length )
{
if(dblArray[2*StartIndex+1]>dblArray[2*StartIndex+2])
{
MinChildrenIndex = 2*StartIndex+2;
}
}
if(dblArray[StartIndex] > dblArray[MinChildrenIndex])
{
ExchageValue(ref dblArray[StartIndex],ref dblArray[MinChildrenIndex]);
StartIndex = MinChildrenIndex ;
}
}
}
/// <summary>
/// exchange value
/// </summary>
/// <param name="A"></param>
/// <param name="B"></param>
private static void ExchageValue(ref double A , ref double B)
{
double Temp = A ;
A = B ;
B = Temp ;
}
[edit] Java Code
import java.util.Arrays;
public class HeapSort {
public static void main(String[] args)
{
int[] arry_int={49,38,65,97,76,13,27,55};
//int[] arry_int={13, 38, 27, 55, 76, 65, 49, 97};
HeapSort hsort=new HeapSort();
hsort.HeapSorting(arry_int);
//System.out.println(Arrays.toString(arry_int));
}
public void HeapAdjust(int[] arr, int s,int m)
{
int temp=arr[s];
for(int j=2*s+1;j<m;j=j*2+1)
{
if(j+1<m && arr[j]>arr[j+1]) ++j;
if(temp<arr[j])break;
arr[s]=arr[j];
s=j;
arr[s]=temp;
}
}
public void HeapSorting(int[] arr)
{
for(int i=(arr.length/2-1);i>=0;--i)
{
HeapAdjust(arr,i,arr.length);
}
for(int j=arr.length-1;j>0;--j)
{
System.out.println("Heap top element arrr[0]="+arr[0]);
System.out.println("arr["+j+"]="+arr[j]);
System.out.println("exchange with"+j+"element");
int temp=arr[0];
arr[0]=arr[j];
arr[j]=temp;
HeapAdjust(arr,0,j);
System.out.println(Arrays.toString(arr));
}
}
}
[edit] VB Code
Option Explicit
Dim Result, I
Dim TestData(100)
const N = 100
Randomize
For I = 0 To N - 1
TestData(I) = ROUND(RND() * 32768)
Next
Sub HSort(byRef Array, low, hi)
Dim i, t, j, p, l, r
For i = hi To low + 1 Step -1
j = i
p = Int((j-low+1)/2)+low-1
t = Array(j)
Do
If p = low-1 Then
Exit Do
End If
If t > Array(p) Then
Array(j) = Array(p)
j = p
p = Int((j-low+1)/2)+low-1
Else
Exit Do
End If
Loop
Array(j) = t
Next
For i = hi To low + 1 Step -1
t = Array(i)
Array(i) = Array(low)
j = low
Do
l = (j-low+1)*2+low-1
If l < i Then
r = (j-low+1)*2+low
If r < i Then
If Array(l) < Array(r) Then
l = r
End If
End If
If t < Array(l) Then
Array(j) = Array(l)
j = l
Else
Exit Do
End If
Else
Exit Do
End If
Loop
Array(j) = t
Next
End Sub
HSort TestData, 0, N - 1
For I = 0 To N - 1
Result = Result & TestData(I) & VbTab
Next
MsgBox(Result)
[edit] Perl Code
#!/usr/bin/perl -w
use strict;
my @numbers = (4, 7, 8, 2, 9, 5, 0, 6, 1, 3);
print_heap(\@numbers); # before
heapsort(\@numbers);
print_heap(\@numbers); # after
exit;
sub heapsort {
my $heap = shift;
my $length = @$heap;
for (my $i = int($length / 2) - 1; $i >= 0; $i--) {
sift($heap, $i, $length);
}
for (my $i = $length - 1; $i > 0; $i--) {
swap($heap, $i, 0);
sift($heap, 0, $i);
}
}
sub sift {
my ($heap, $i, $n) = @_;
while ($i <= int($n / 2) - 1) {
my $child = (($i + 1) * 2) - 1;
if ($child + 1 <= $n - 1) {
if ($$heap[$child] < $$heap[$child + 1]) {
$child++;
}
}
if ($$heap[$i] < $$heap[$child]) {
swap($heap, $i, $child);
$i = $child;
} else {
last;
}
}
}
sub swap {
my ($heap, $i, $j) = @_;
@{$heap}[$i, $j] = @{$heap}[$j, $i];
}
sub print_heap {
my $heap = shift;
print join(" ", @$heap) . "\n";
}
[edit] Prolog Code
This section needs your Code!
[edit] Python Code
def heapify(a, start, count):
root = start
while root * 2 + 1 < count:
child = root * 2 + 1
if child < count - 1 and a[child] < a[child + 1]:
child += 1
if a[root] < a[child]:
a[root], a[child] = a[child], a[root]
root = child
else:
return
def heapsort(a):
count = len(a)
start = count / 2 - 1
end = count - 1
while start >= 0:
heapify(a, start, count)
start -= 1
while end > 0:
a[end], a[0] = a[0], a[end]
heapify(a, 0, end)
end -= 1
[edit] Ruby Code
module HeapSort
def self.sort(keys)
sort!(keys.clone)
end
def self.sort!(keys)
build_max_heap(keys)
(keys.size-1).downto(1) do |i|
keys[0], keys[i] = keys[i], keys[0]
max_heapify(keys, i, 0)
end
keys
end
private
def self.build_max_heap(keys)
(keys.size/2-1).downto(0) do |i|
max_heapify(keys, keys.size, i)
end
keys
end
def self.max_heapify(keys, size, i)
l = 2*i+1
r = 2*i+2
if l < size and keys[l] > keys[i]
largest = l
else
largest = i
end
if r < size and keys[r] > keys[largest]
largest = r
end
if (largest != i)
keys[i], keys[largest] = keys[largest], keys[i]
max_heapify(keys, size, largest)
end
end
end
