由于堆排序是一种非常漂亮的排序，是算法与数据结构结合的典例，所以单独拿出来说说哈。

什么是堆

以最大值堆（大根堆）为例。大根堆是一棵完全二叉树，且二叉树上每一个节点R有：R的关键码大于等于其两个直接孩子的关键码。简而言之堆是一种局部有序的完全二叉树。由于堆是完全二叉树，所以利用数组来实现堆的空间利用率是最高的。

完全二叉树，

首先满二叉树是指，树上的每一个节点，其左子树高度==右子树高度。那么高度为h的完全二叉树就是前h-1层为满二叉树，最后一层节点从左向右连续出现。

完全二叉树的判断

由完全二叉树的逐层由左往右铺满的构造形态可以联想到利用树的层次遍历来判断完全二叉树。注意为了达到从左往右遍历铺满的目的，每一个节点的左孩子应该先于右孩子进入队列。假设当前出队的节点R（遍历到R），若在判断R的子节点时出现空子节点，则停止遍历，如果是完全二叉树，那么此时所有的节点都应进入过队列；否则必然不是完全二叉树。

// 伪代码
class Node {
    Node l, r;  // 左子节点，右子节点
    int value;
}
public boolean isFullBinaryTree(Node root, int treeSize) {
    Queue<Node> q = new LinkedList<>();
    int cnt = 1;
    q.add(root);
    while (!q.isEmty()) {
        Node u = q.poll();
        if (u.l == null) break;
        else {
            q.add(u.l); cnt += 1;
        }
        if (u.r == null) break;
        else {
            q.add(u.r); cnt += 1;
        }
    }
    return cnt == treeSize;
}

堆的判断

在二叉树是完全二叉树的基础上，我们来继续判断堆，只需要利用堆的局部有序性即可。就是遍历堆的每一个非叶子节点R，判断R的关键码是否大于等于其子节点。

// 伪代码
// 大小为heapSize的堆的最后一个下标为heapSize-1
// 则第一个分支节点是最后一个叶子节点的父亲 => 下标为(heapSize-1-1)/2
public boolean isHeap(int[] heap, int heapSize) {
    for (int i = (heapSize-2) >> 1; i >= 0; --i) {
        int l = (i<<1) + 1, r = l;
        if (l + 1 < heapSize) r = r + 1;
        if (heap[i] < heap[l] || heap[i] < heap[r])
            return false;
    } return true;
}

堆排序

堆排序就是利用了堆的根绝对最值的性质来实现。由于堆根节点的删除是将根与最后一个叶子节点交换，之后上推下拉维护大小减一的新堆。实际上每一次“删除”都将当前的最值放到了“最后”，所以要升序排序，应构建最大值堆：要降序排序，应构建最小值堆。

public void shift_down(int arr[], int t, int n) {
    while (t < n) {
        int lef = (t<<1) + 1, rig = lef + 1;
        if (rig < n && arr[lef] < arr[rig]) // 方便之后统一与lef指针交换
            lef = rig;
        if (lef < n && arr[t] < arr[lef]) {
            swap(arr[t], arr[lef]);
            t = lef;
        } else break;
    }
}

// 交换建堆法O(n)，构建最大值堆
// 从第一个非叶子节点开始，进行下拉操作
public void make_heap(int arr[], int n) {
    for (int i = (n-2) >> 1 ; i >= 0; --i) {
        shift_down(arr, i, n);
    }
}

public void pop_heap(int[] arr, int n) {
    // 删除
    swap(arr[0], arr[n - 1]);
    // 维护大小-1的堆
    shift_down(arr, 0, n - 1);
}

public void heap_sort(int[] arr, int n) {
    make_heap(arr, n);
    for (int i = n; i > 1; --i) {
        pop_heap(arr, i);
    }
}

堆排序

原文：https://www.cnblogs.com/GorgeousBankarian/p/12528417.html