【算法导论】之堆排序

时间：2021-04-08 19:05:24

堆的简介

    一般说堆，说的是二叉堆。堆数据结构是一种数组对象，它可以被看作为一棵完全二叉树。树中的每个节点与数组中存放该节点值的那个元素对应。

    堆有两个属性:堆能容纳的元素个数，堆中存放的元素个数。二叉堆有两种：大根堆和小跟堆，它们应该满足的性质：A[parent[i]]>=A[i]或A[parent[i]]<=A[i]。以下就是一个大根堆。

【算法导论】之堆排序

堆的操作

保持堆的性质

Heap * init_heap(){
    Heap *p = (Heap *)malloc(sizeof(Heap));
    p->array_addr = NULL;
    p->capacity = 0;
    p->size = 0;
    return p;
}
/**调整heap中的第i个节点子树为大根堆**/int heap_adjust(Heap * const heap,const int i){    if(heap == NULL || heap != NULL && heap->array_addr == NULL) return 0;    int left = i * 2 +1 ;    int right = i * 2 + 2;    int largest = i;    int swap = 0;    if(left < heap -> size && *(heap->array_addr + left) > *(heap->array_addr + largest))        largest = left;    if(right < heap -> size && *(heap->array_addr + right) > *(heap->array_addr + largest))        largest = right;    if(largest != i){        swap =  *(heap->array_addr + i);        *(heap->array_addr + i) = *(heap->array_addr + largest);        *(heap->array_addr + largest) = swap;        return heap_adjust(heap,largest);    }    return 1;}

/**构建大根堆   从下向上构建大根堆**/int build_heap(Heap * const heap){    if(heap == NULL || heap != NULL && (heap->array_addr == NULL || heap->capacity <= 0)){        return 0;    }    int i = (heap->capacity-1) / 2;    for(;i >= 0;i--){        heap_adjust(heap,i);    }    return 1;}

堆排序

/**将堆顶元素与尾部元素对换
   调整堆
**/
int heap_sort(Heap * const heap){
    if(heap == NULL) return 0;
    if(build_heap(heap)){
        int i = heap -> capacity -1;
        int swap = 0;
        for(;i > 0 ;i--){
            swap = *(heap -> array_addr + i);
            *(heap -> array_addr + i) = *(heap -> array_addr + 0);
            *(heap -> array_addr + 0) = swap;
            heap -> size = heap -> size -1;
            heap_adjust(heap,0);
        }
        return 1;
    }else return 0;
}

优先队列

    优先级队列支持如下操作：
    1)取出最大元素，但不移除。
    2)抽取最大元素
    3)在指定位置，用key取代A[i]的值，但key必须比A[i]要大
    4)在队列中增加元素 
/**返回优先队列最大元素*/
int heap_max(Heap * const heap){
   if(heap == NULL || heap -> size <1){
        return -1;
   }
   return *(heap -> array_addr + 0);
}

/**A[0]与末位元素对调
    从上至下调整队列
**/
int extract_max(Heap * const heap){
   if(heap == NULL || heap -> size < 1 || heap -> array_addr == NULL) return -1;
   int max = *(heap -> array_addr + 0);
   *(heap -> array_addr + 0) = *(heap -> array_addr + heap -> size -1);
   heap -> size -= 1;
   heap_adjust(heap,0);
   return max;
}

int increase_key(Heap * const heap,int i,int key){   if(heap == NULL || heap -> size < 1 || heap -> array_addr == NULL) return -1;   if(key < *(heap -> array_addr + i)) return -1;   *(heap -> array_addr + i) = key;   int index = i;   int swap = 0;   while(index > 0 && *(heap -> array_addr + index) > *(heap -> array_addr + index / 2)){      swap = *(heap -> array_addr + index);      *(heap -> array_addr + index) = *(heap -> array_addr + index / 2);      *(heap -> array_addr + index / 2) = swap;      index /= 2;   }}int heap_insert(Heap * const heap,int key){   if(heap == NULL || heap -> size < 1 || heap -> array_addr == NULL) return -1;   heap -> size += 1;   *(heap -> array_addr + index) = INT_MIN;   increase_key(heap,heap -> size - 1,key);   return 1;}




标签：

相关文章