Êý¾Ý½á¹¹ÓëË㷨ѧϰ±Ê¼Ç¡ª¡ª¶ÑÅÅÐò

/**********************************************************************
* Copyright(C):
* Filename    : heapsort.c
* Author      :
* Version     :
* Date        :
* Description :
**********************************************************************/

#include "heapsort.h"


//------------------------------------------
// MaxHeapify(ElementType A[], int i, int heap_size){
// maintain the max-heap property 
// 
//
void MaxHeapify(ElementType A[], int i, int heap_size){
 int l = LEFT(i);
 int r = RIGHT(i);
 int largest = i;

 if ( l < heap_size-1 && A[l] > A[largest] ){
  largest = l;
 }
 if ( r < heap_size-1 && A[r] > A[largest] ){
  largest = r;
 }

 if ( largest != i ){
  ElementType a = A[ i ];
  A[ i ] = A[ largest ];
  A[ largest ] = a;

  MaxHeapify(A,largest,heap_size);
 }
}


//------------------------------------------
// BuildMaxHeap(ElementType A[], int N)
// Build max-heap
//
//
void BuildMaxHeap(ElementType A[], int N){
 int i;
 int heap_size = N;
 for (i=(N-1)/2; i>=0; i--){
  MaxHeapify(A,i,heap_size);
 }
}


//------------------------------------------
// HeapSort(ElementType A[], int N)
// heap sort algorithm
//
//
void HeapSort(ElementType A[], int N){
 int i;
 ElementType tmp;
 BuildMaxHeap(A,N);
 for (i=N-1; i>=1; i--){
  tmp = A[ 0 ];
  A[ 0 ] = A[ i ];
  A[ i ] = tmp;
  N--;
  MaxHeapify(A,0,N);
 }
}

/***********************************************************************
* Copyright(C):
* Filename    : heapsort.h
* Author      :
* Version     :
* Date        :
* Description :
***********************************************************************/

#ifndef ALGRTHM_HEAP_SORT_H
#define ALGRTHM_HEAP_SORT_H

#define LEFT(x)     ((x)<<1);
#define RIGHT(x)    (((x)<<1)+1)

typedef int ElementType;

//-------API function declaration--------------------

void HeapSort(ElementType A[], int N);

#endif // ALGRTHM_HEAP_SORT_H