算法导论：c++堆排序&优先队列

向右看齐 2022-06-04 01:38 236阅读 0赞

预习了一下算法导论的堆排序，以前数据结构课简直是一知半解。  
![这里写图片描述][SouthEast]

![这里写图片描述][SouthEast 1]  
建大根堆的过程为从数组中间向左遍历，然后不断调整左右子树使得最大数处于根节点。一开始以为堆排序一定要用二叉树还写了个傻傻的建树程序。。。

### 数组调整为大根堆 ###

/*调整大根堆*/
    void max_heapify(int data[], int cur, int heapsize)
    {
        int left = 2 * cur + 1;
        int right =left+1;
        int largest = cur;
        if (left<heapsize && data[left] > data[largest]) {
            largest = left; //最大为左子树
        }
        if (right<heapsize && data[right] > data[largest]) {
            largest = right;//最大为右子树
        }
        if (largest != cur) //根不是最大，则要交换
        {
            int temp = data[cur];
            data[cur] = data[largest];
            data[largest] = temp;
            max_heapify(data, largest, heapsize); //继续调整
        }
    }
    /*建立大根堆*/
    void build_max_heap(int data[], int heapsize) 
    {   //只需要对除了叶子节点以外的节点进行调整
        for (int i = heapsize / 2 - 1; i >= 0; i--) {
            max_heapify(data, i, heapsize);
        }
    }

测试一下，输入一个数组

int main()
    {
        const int len = 9;
        int array[len] = { 1,2,3,4,5,6,7,8,9};
        //convertArray2Tree(array,len);
        build_max_heap(array, len);
        for (int i = 0; i < len; i++)
        {
            cout << array[i] << " ";
        }
    }

> 调整后输出为：9 8 7 4 5 6 3 2 1

### 堆排序 ###

![这里写图片描述][SouthEast 2]  
调整为大根堆后继续进行排序，将数组的头和最尾元素进行交换后再调整，把次大调整到数组头，再继续

/*堆排序*/
    void heap_sort(int data[], int heapsize)
    {
        build_max_heap(data, heapsize);
        for (int i = heapsize - 1; i>0; i--) //交换调整后的数组第一个元素和最后一个元素，再调整
        {
            int temp = data[0];
            data[0] = data[i];
            data[i] = temp;
            max_heapify(data,0,i);
        }
    }

> 调整后输出:1 2 3 4 5 6

## 优先队列 ##

![这里写图片描述][SouthEast 3]

![这里写图片描述][SouthEast 4]  
实现优先队列返回最大和删除最大：

/*堆实现优先队列返回最大*/
    int heap_maximum(int data[], int heapsize)
    {
        return data[0];
    }
    /*堆实现返回优先队列最大并删除*/
    int heap_extract_max(int data[], int heapsize)
    {
        int max = data[0];
        data[0] = data[heapsize - 1]; //将最后一个元素放到第一
        heapsize = heapsize - 1; //删除一个元素
        max_heapify(data, 0, heapsize);  //调整
        return heapsize;
    }

接上文的输入用例，删除最大元素9

int main()
    {
    
        const int len = 9;
        int array[len] = { 1,2,3,4,5,6,7,8,9};
        build_max_heap(array, len);
        int lenNew = heap_extract_max(array, len);
    
        for (int i = 0; i < lenNew; i++)
        {
            cout << array[i] << " ";
        }
    }

> 输出：8 5 7 4 1 6 3 2

![这里写图片描述][SouthEast 5]

![这里写图片描述][SouthEast 6]  
实现增加第8个元素值至15。

/*增加值*/
    void heap_increase_key(int data[], int heapsize, int i, int key) 
    {
        if (data[i] > key) {
            return;
        }
        data[i] = key;
        while (i>=0 && data[(i - 1) / 2]<data[i]) //当前父节点比当前节点小，需要交换
        {
            int temp = data[i];
            data[i] = data[(i - 1) / 2];
            data[(i - 1) / 2] = temp;
            i = (i - 1) / 2;
        }
    }
    int main()
    {
    
        const int len = 10;
        int array[len] = { 16,14,10,8,7,9,3,2,4,1};
        //convertArray2Tree(array,len);
        build_max_heap(array, len);
        heap_increase_key(array, len, 8, 15);
        for (int i = 0; i < len; i++)
        {
            cout << array[i] << " ";
        }
    
    }

输入同文章中相同

> 输出：16 15 10 14 7 9 3 2 8 1

[SouthEast]: /images/20220604/06375bc4637b4176b8515efe1f844be9.png
[SouthEast 1]: /images/20220604/bdec7b035f7c4193ae3ba36d41e9f5b9.png
[SouthEast 2]: /images/20220604/5335e80e219e4fd697bada6a2af3bf2b.png
[SouthEast 3]: /images/20220604/a717edb05c544d0faa3a214e009f5464.png
[SouthEast 4]: /images/20220604/767203fc868a402d897019abd62f5f8d.png
[SouthEast 5]: /images/20220604/3b9d338cc3b04a8688a7c28eb7cf3a8a.png
[SouthEast 6]: /images/20220604/0bae8e43378243d7a6048aa79228c938.png