美文网首页
堆和堆排序

堆和堆排序

作者: 狗尾巴草败了 | 来源:发表于2017-08-21 16:15 被阅读0次

    堆:

    堆是具有下列性质的完全二叉树
    每个节点的值都大于或等于左右孩子节点的值,称为大顶堆
    每个节点的值都小于或等于左右孩子节点的值,称为小顶堆

    堆排序

    #include <iostream>
    using namespace std;
    /******************堆排序************************/
    void AdjustHeap(int arr[], int s, int m) {
        int temp = arr[s];
        for(int j = 2*s+1; j <= m; j *= 2 + 1) {
            if(j < m && arr[j] < arr[j+1])
                j++;
            if(temp > arr[j])
                break;
            arr[s] = arr[j];
            s = j;
        }
        arr[s] = temp;
    }
    void HeapSort(int arr[], int length) {
        if(length <= 0)
            return;
        for(int i = length/2 -1; i >= 0; --i) {
            AdjustHeap(arr, i, length-1);
        }
        for(int i = length -1; i > 0; --i) {
            swap(arr[0], arr[i]);
            AdjustHeap(arr, 0, i-1);
        }
    }
    

    相关文章

      网友评论

          本文标题:堆和堆排序

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