1.维护堆

#LEFT(i)和RIGHT(i)为 i 节点的左右子孩子，以最大堆为例。

首先输入为一个数组A和一个下标i。假定根节点为LEFT(i)和RIGHT(i)的二叉树都是最大堆，但这时A[i]有可能小于其孩子，这样就违背了最大堆的性质。维护堆通过让A[i]的值在最大堆中“逐级下降”，从而使得以下标i为根节点的子树重新遵循最大堆的性质。

 

主要过程：从A[i]，A[LEFT(i)]和A[RIGHT(i)]中选出最大的，并将其下标存储在largest中。

1.如果A[i]是最大的，那么以 i 为根节点的树已经是最大堆，维护结束。

2.否则，最大元素是 i 的某个孩子节点，则交换A[i]和A[largest]的值。从而使 i 及其孩子都满足最大堆的性质。在交换后，下标为largest的节点的值是原来的A[i]，于是以该节点为根的子树又有可能会违反最大堆的性质。因此，需要对该子树递归进行维护堆的过程。

 

2.建堆

从初始输入数组建成的完全二叉树的最后一个非叶节点开始，向上至根节点，每个节点都进行维护堆，即可形成最大堆。

 

3.堆排序

建堆完成后，已将输入数组A[1...n]建成最大堆。因为数组中的最大元素总在根节点A[1]处，通过把它与A[n]互换，并把它放到正确位置。然后从堆中删除节点n。此时，新的根节点可能会违背最大堆的性质。然后就要从根节点开始维护堆，构造一个新的最大堆。不断重复这一过程，直到堆里还剩一个节点。

import math.random def print_tree(array):  # 打印堆排序使用        """       深度 前空格 元素间空格    1     7       0    2     3       7    3     1       3    4     0       1    """    # first=[0]    # first.extend(array)    # array=first    index = 1    depth = math.ceil(math.log2(len(array))) # 因为补0了，不然应该是math.ceil(math.log2(len(array)+1))    sep = '  '    for i in range(depth):        offset = 2 ** i        print(sep * (2 ** (depth - i - 1) - 1), end='')        line = array[index:index + offset]        for j, x in enumerate(line):            print("{:>{}}".format(x, len(sep)), end='')            interval = 0 if i == 0 else 2 ** (depth - i) - 1            if j < len(line) - 1:                print(sep * interval, end='')        index += offset        print()def sort(arr,start,end):    if end == start * 2:        if arr[start * 2] > arr[start]:            arr[start * 2], arr[start] = arr[start], arr[start * 2]    else:        if end < start * 2 + 1:            return        else:            left = arr[start*2]            right = arr[start*2+1]            if left>right and left > arr[start]:                arr[start * 2 ], arr[start] = arr[start], arr[start * 2 ]                sort(arr,start*2,end)            if left
     
       arr[start]:                arr[start * 2+1], arr[start] = arr[start], arr[start * 2+1]                sort(arr, start * 2+1, end)def heapfiy(arr):    x = len(arr) - 1    n = x // 2    while n > 0:        # print(n)        sort(arr, n, x)        n -= 1# 以下是主函数# 第一个0是占位用orignal_list=[0, 74, 73, 59, 72, 64, 69, 43, 36, 70, 61, 40, 16, 47, 67, 17, 31, 19, 24, 14, 20, 48, 5, 7, 3, 78, 84, 92, 97, 98, 99]print(orignal_list)# 第一次构建最大堆heapfiy(orignal_list)# 打印树print_tree(orignal_list)x = len(orignal_list) - 1while x != 1:    # 交换最大的数和最后一个    orignal_list[1],orignal_list[x]=orignal_list[x],orignal_list[1]    x-=1    # 由于交换了，不再是最大堆，重新构建最大堆    n=x//2    while n>0:        sort(orignal_list,n,x)        n-=1# 打印最后结果print_tree(orignal_list)print(orignal_list)
     

 

c++：

#include
     
      using namespace std; void heapSort(int a[], int n);void maxHeap(int a[], int n);void buildMaxHeap(int a[], int n); int size;int main(){    int a[] = { 9, 12, -3, 0, 6, 8, 15, 7 };    size= sizeof(a) / 4;    heapSort(a, size);    for (int i = 0; i < 8; i++)        cout << a[i] << " ";    return 0;}void heapSort(int a[], int n){    int i;    buildMaxHeap(a, n);    for (i = size; i>1; i--)    {        swap(a[0], a[i-1]);        size = size - 1;        maxHeap(a, 1);      } }void buildMaxHeap(int a[], int n){    int i = n / 2;    for (i; i > 0; i--)        maxHeap(a, i); }void maxHeap(int a[], int n){    int leftChild, rightChild, largest;    leftChild = 2 * n;    rightChild = 2 * n + 1;    int q = sizeof(a);    if (leftChild<=size&&a[leftChild-1]>a[n-1])        largest = leftChild;    else        largest = n;    if (rightChild<=size&&a[rightChild-1]>a[largest-1])        largest = rightChild;    if (largest != n)    {                swap(a[n-1], a[largest-1]);        maxHeap(a, largest);    }}
     

 

优先队列

优先队列是一种用来维护由一组元素构成的集合S的数据结构，其中每一个元素都有一个相关值，称为关键字。

一个最大优先队列支持以下操作：

1.返回S中具有最大关键字的元素

2.去掉并返回S中具有最大关键字的元素

3.将元素x的关键字值增加到k，这里假设k的值不小于原关键字的值。

4.把元素x插入到集合S中

 

以下给出实现思想(在已建成最大堆的基础上)：

1.返回根节点即可

2.通过维护堆(具体过程参考堆排序)，即可实现去掉最大关键字

3.通过不断与其父节点比较和交换，寻找正确位置，维护最大堆的性质

4.在堆中为x增加一个叶节点，然后通过3的过程为x寻找正确位置