- #include
- #include
- #include"heap.h"
- int heap_init(Heap *heap,int maxlen)
- {
- heap->array = (int *)malloc(maxlen*sizeof(int));
- if(heap->array == NULL)
- {
- printf("malloc failed for heap_init\n");
- return -1;
- }
- heap->maxlen = maxlen;
- heap->number = 0;
- return 0;
- }
int heap_destroy(Heap* heap)
{
if(heap->array)
free(heap->array);
heap->array = NULL;
heap->number = 0;
heap->max->len = 0;
return 0;
}
- void inline swap(int *x ,int *y)
- {
- int temp =*x;
- *x = *y;
- *y = temp;
- }
- void heap_fixup(int array[],int pos)
- {
- while(pos>0 && array[pos]
- {
- swap(&array[pos],&array[father(pos)]);
- pos = father(pos);
- }
- }
- void heap_fixdown(int array[],int pos,int rlmit)
- {
- int j;
- while(firstson(pos) <= rlimit)
- {
- j = firstson(pos);
- if(j < rlimit && array[j] >array[j+1])
- j++;
- if(array[pos] < array[j])
- break;
- swap(&array[pos],&array[j]);
- pos = j;
- }
-
- }
- int heap_insert(Heap* heap,int value)
- {
- if(heap->number +1 >(heap->maxlen))
- {
- int *new_array = realloc(heap->array,(heap->maxlen)*2);
- if(new_array == NULL)
- {
- printf("realloc for heap_insert failed\n");
- return -1;
- }
- heap->array = new_array;
- heap->maxlen = heap->maxlen <<1;
- }
-
- heap->array[heap->number] = value;
- heap_fixup(heap->array,heap->number);
- heap->number++;
- return 0;
-
- }
- int heap_delmin(Heap *heap)
- {
- swap(&(heap->array[0]),&(heap->array[heap->number-1]));
- heap->number--;
- heap_fixdown(heap->array,0,heap->number-1);
- return heap->array[heap->number];/*return the smallest element */
- }
- int heapsort(int array[],int left,int right)
- {
- int len;
- Heap heap;
- int ret;
- int pos;
-
- if(array == NULL)
- {
- return -1;
- }
- if(left > right)
- {
- return -2;
- }
- if(left == right)
- {
- return 0;
- }
- len = right - left + 1;
- ret = heap_init(&heap,len);
- if(ret <0)
- return ret;
- for(pos = left ;pos<=right;pos++)
- heap_insert(&heap,array[pos]);
- for(pos = left ; pos <= right; pos++)
- array[pos] = heap_delmin(&heap);
- heap_destroy(&heap)
- return 0;
- }
int heapsort2(int array[],int left ,int right)
{
if(array == NULL)
{
return -1;
}
if(left > right)
{
return -2;
}
if( left == right )
{
return 0;
}
int len = right - left + 1;
int i;
int * base = &(array[left]);
for(i = father(len-1); i >=0; i --)
{
heap_fixdown(base,i,len-1);
}
while(len >0)
{
swap(&base[0], &base[len-1]);
len--;
heap_fixdown(base,0,len-1);
}
/*由于是最小堆,同时从小到大排序,所以需要将数组翻转。如果是最大堆就不用翻转了*/
int mid = (right+left)/2;
for(i = left ;i <= mid;i++)
{
swap(&array[i],&array[left+right - i]);
}
return 0;
}