堆排序及其c语言实现

堆的性质：堆是一棵完全二叉树，它有最大堆和最小堆之分，这里只分析最大堆！（最小堆与最大堆类似）就是所有的子节点都小于根节点的完全二叉树

堆的几种操作（数组实现）：其中 len 表示数组长度，headsize表示堆的长度

其中堆的左节点编号

int LEFT(int i )
{
  return i*2;
}

堆的右节点编号：

int RIGHT(int i )
{
   return i*2 +1;
}

堆的头结点编号

int PARENT(int i )
{
   return i/2;
}

1.保持堆的性质：

void MAX_HEAPIFY(int A[],int i)
{
  int l = LEFT(i);
  int r = RIGHT(i);
  int largest;
  if( l<= heapsize && A[l] > A[i])
      largest = l;
  else largest = i;
  if(r <= heapsize && A[r] > A[largest])
     largest = r;  //找出本节点以及其儿子节点最大的值的编号
  if(i != largest)
    {
      int temp = A[i];
      A[i] = A[largest];
      A[largest] = temp;
      MAX_HEAPIFY(A,largest);//子树可能交换后不保持性质，使起保持性质
    }

}

View Code

2.建堆 O( nlgn)

void BUILD_MAX_HEAP(int A[])
{
   heapsize = len;
   for(int i = len/2 ;i >= 1;i --)
      MAX_HEAPIFY(A,i);
}

View Code

3.堆排序 O(nlgn)

void HEAPSORT(int A[])
{
   BUILD_MAX_HEAP(A);
   for(int i = len ;i >= 2;i --)
     {
       int temp = A[1];
       A[1] = A[i];
       A[i] = temp;
       heapsize = heapsize - 1;
            }
}

View Code

4.找出堆的最大值 O(1)

int HEAP_MAXIMUM(int A[])
{
   return A[1];
}

View Code

5.找出堆的最大值并删除它 O(lgn)

int HEAP_EXTRACT_MAX(int A[])
{
   if(heapsize < 1)
      {
        printf("heap underflo");
        exit(0);
      }
   int max = A[1];
   A[1] = A[heapsize];
   heapsize = heapsize - 1;
   MAX_HEAPIFY(A,1);
   return max;
}

View Code

6.将某元素的的值增加到某值 O(lgn)

 1 void HEAP_INCREASE_KEY(int A[],int i,int key)
 2 {
 3   if(key < A[i])
 4     {
 5        printf("new key is smaller than current key");
 6        exit(0);
 7     }
 8   A[i] = key;
 9   while(i > 1 and A[PARENT(i)] < A[i] )
10    {
11      int temp = A[PARENT(i)];
12      A[PARENT(i)] = A[i];
13      A[i] = temp;
14      i = PARENT(i);
15    }//向上更新
16 
17 }

View Code

7.加入到某值 O(lgn)

void MAX_HEAP_INSERT(int A[],int key)
{
    heapsize = heapsize +1;
    A[heapsize] = INT_MIN;
    HEAP_INCREASE_KEY(A,heapsize,key);
}

View Code

其中堆排序没有响应的删除算法，只有朴素思路。。

没有梦想，何谈远方