堆排序

作者: 赵星宇 | 来源:发表于2014-06-25 23:59 被阅读127次

    堆是一个完全二叉树的数组对象。树的每一层都是满的,最后一层可能除外(因为从一个节点的左子树开始填)。

    例如

    0-1-2-3-4(索引)
    16-14-10-2-1(值)

    节点位置计算

    给定一个节点,可以很容易的计算父节点和子节点的位置。
    parent(i)=floor((i-1)/2)
    leftChild=2(i+1)-1
    rightChild=2
    (i+1)
    注意:可以将乘2算法变成向左移位,除2算法变成向右移位。
    即:
    parent(i)=(i-1)>>1
    leftChild=(i+1)<<1-1
    rightChild=(i+1)<<1

    堆排序

    堆排序的时间复杂度为O(nlogn)是比较有效率的一种。其使用的是最大堆。最大堆的意思是父节点的值>=孩子节点的值。所以,堆排序每次循环把最大值移走,然后从剩下的节点重新建立最大堆。

    第一步:

    首先定义堆的结构体

    typedef struct heap_t{
        int *arr;//point for an array to store heap value.
        int heapMaxIndex;//heap element max index number
        int arrLength;//array length of arr
    } Heap;
    

    其中arr指针指向的是存放堆数据的数组。
    heapMaxIndex是堆的最大序号。比它小的都属于堆。
    arrLength是数组最大的序号。如数组定义为a[10],那么arrLength的值应该为9。

    第二步:

    保持堆的性质
    这一步是堆排序的基础。这里将功能写成一个函数名为void maxHeapify(Heap *hp, unsigned int nodei),这个函数用于让一个数组变成一个符合堆性质的数组。时间复杂度为O(h),h是堆所属二叉树的高度=logn(n是节点个数)。
    思想:
    从一个节点i,和它的孩子leftChild(i)和rightChild(i)中找到最大的,然后其索引存放在largest中。如果i的值是最大的。那么i为根的子树已经是最大堆,程序结束。
    如果i的值不是最大的,那么将i的值和largest的值交换。下标为largest的节点在交换后作为父节点,那么它有可能违反堆的性质,因此递归调用该函数。

    void maxHeapify(Heap *hp, unsigned int nodei) {
        unsigned int l = (nodei + 1) << 1 - 1;//left child
        unsigned int r = (nodei + 1) << 1;//right child
        unsigned int largest = 0;
        int heapMaxI = hp->heapMaxIndex;
        if(l <= heapMaxI && hp->arr[l] > hp->arr[nodei])
            largest = l;
        else
            largest = nodei;
        if(r <= heapMaxI && hp->arr[r] > hp->arr[largest])
            largest = r;
    
        if(largest!=nodei) {
            swap(&(hp->arr[largest]), &(hp->arr[nodei]));
            maxHeapify(hp, largest);
        } else
            return ;
    }
    
    第三步 利用maxHeapify函数创建堆

    对于1个size为n的堆,我们可以分析到,n/2-1之前的都是父节点,其他的都是叶子节点,我们只需要对父节点进行maxHeapify就可以了。
    n/2可以用右移运算n>>1。

    Heap* createHeap(int* arrp,int  arrMaxIndex, int arrLength) {
        Heap* heap = malloc(sizeof(Heap));
        assert(heap!=NULL);
        heap->arr = arrp;
        heap->heapMaxIndex = arrMaxIndex;
        heap->arrLength = arrLength;
        int i;
        for(i = (arrMaxIndex + 1) >> 1 - 1; i >=0; i--)
            maxHeapify(heap, i);
        return heap;
    }
    
    第四步 堆排序

    设堆的数组为A[0..n-1],调用maxHeapify函数就可以得到最大值,然后将最大值和n-1互换,把堆的大小heapMaxIndex减1,再次调用maxHeapify,又得到最大值,存放在A[0],再和A[n-2]互换,把堆的大小再减一,这样循环下去,直到堆的大小为0。那么我们就得到了从小到大的排好序的数组。

    void heapSort(Heap* hp) {
        int last;
        while(hp->heapMaxIndex > 0) {
            last = hp->heapMaxIndex;
            swap(&(hp->arr[0]), &(hp->arr[last]));
            hp->heapMaxIndex -= 1;
            maxHeapify(hp, 0);
        }
    }
    
    第五步 测试堆排序
    int main(void) {
        int array[] = {15,25,32,23,1,-4,35,2,-85,42,0,12,26,56,45,12,145,17,25,21};
        printArr(array, getSize(array));
        Heap* hp = createHeap(array, getSize(array)-1, getSize(array));
        heapSort(hp);
        printArr(array, getSize(array));
        freeHeap(hp);
        return 0;
    }
    

    完整的程序如下

    #include <stdio.h>
    #include <assert.h>
    #include <stdlib.h>
    typedef struct heap_t{
        int *arr;//point for an array to store heap value.
        int heapMaxIndex;//heap element max index number
        int arrLength;//array length of arr
    } Heap;
    #define getSize(array) (sizeof array / sizeof *array)
    Heap* createHeap(int* arrp,int  arrMaxIndex, int arrLength);
    void swap(int* a, int* b);
    void heapSort(Heap* hp);
    void freeHeap(Heap* heap);
    void maxHeapify(Heap *hp, unsigned int nodei);
    void printArr(int *p, int size);
    int main(void) {
        int array[] = {15,25,32,23,1,-4,35,2,-85,42,0,12,26,56,45,12,145,17,25,21};
        printArr(array, getSize(array));
        Heap* hp = createHeap(array, getSize(array)-1, getSize(array));
        heapSort(hp);
        printArr(array, getSize(array));
        freeHeap(hp);
        return 0;
    }
    
    void swap(int* a, int* b) {
        int tmp;
        tmp = *a;
        *a = *b;
        *b = tmp;
    }
    
    Heap* createHeap(int* arrp,int  arrMaxIndex, int arrLength) {
        Heap* heap = malloc(sizeof(Heap));
        assert(heap!=NULL);
        heap->arr = arrp;
        heap->heapMaxIndex = arrMaxIndex;
        heap->arrLength = arrLength;
        int i;
        for(i = (arrMaxIndex + 1) >> 1 - 1; i >=0; i--)
            maxHeapify(heap, i);
        return heap;
    }
    
    void heapSort(Heap* hp) {
        int last;
        while(hp->heapMaxIndex > 0) {
            last = hp->heapMaxIndex;
            swap(&(hp->arr[0]), &(hp->arr[last]));
            hp->heapMaxIndex -= 1;
            maxHeapify(hp, 0);
        }
    }
    
    void freeHeap(Heap* heap) {
        free(heap);
    }
    
    void maxHeapify(Heap *hp, unsigned int nodei) {
        unsigned int l = (nodei + 1) << 1 - 1;//left child
        unsigned int r = (nodei + 1) << 1;//right child
        unsigned int largest = 0;
        int heapMaxI = hp->heapMaxIndex;
        if(l <= heapMaxI && hp->arr[l] > hp->arr[nodei])
            largest = l;
        else
            largest = nodei;
        if(r <= heapMaxI && hp->arr[r] > hp->arr[largest])
            largest = r;
    
        if(largest!=nodei) {
            swap(&(hp->arr[largest]), &(hp->arr[nodei]));
            maxHeapify(hp, largest);
        } else
            return ;
    }
    void printArr(int *p, int size) {
        int i;
        for(i = 0; i < size; i++) {
            printf("%d ", p[i]);
        }
        printf("\n");
    }
    

    相关文章

      网友评论

        本文标题:堆排序

        本文链接:https://www.haomeiwen.com/subject/wddjtttx.html