28 | 堆和堆排序：为什么说堆排序没有快速排序快？

开局之前

感觉堆这种数据结构很重要，因为优先队列中用到了这种结构
topk也用到了这种结构

什么样的树才是堆呢？

1. 堆是一个完全二叉树

除了最后一层，其余的都是满的，而且最后一层必须靠左对齐

1. 堆中每个节点都要>=或<= 子树中每个节点的值

   对于每个节点的值都大于等于子树中每个节点值的堆，我们叫做“大顶堆”。对于每个节点的值都小于等于子树中每个节点值的堆，我们叫做“小顶堆”。

   所以使用topk的时候 我们都用的是小顶堆，因为堆顶是最小的，只要删除了堆顶元素就可以了

堆化

因为堆化是沿着二叉树的路径走的，所以时间复杂度和高度有关 树的高度不会超过
所以时间复杂度是log2n

从下往上

可以理解为把一个元素插入到最尾部，然后使用节点之间的位置关系，来调整堆

public static void main(String[] args) {
/*
        int arr[] = {5, 98, 78, 15, 32, 2, 46};
        heapSort(arr, arr.length);
        System.out.println(Arrays.toString(arr));;
        */
        Heap heap = new Heap(10);
        heap.insert(1);
        heap.insert(2);
        heap.insert(3);
        heap.insert(4);
        heap.insert(5);
        System.out.println(1);
    }
    public static class Heap {
        private int[] a; // 数组，从下标1开始存储数据
        private int n;  // 堆可以存储的最大数据个数
        private int count; // 堆中已经存储的数据个数
        public Heap(int capacity) {
            a = new int[capacity + 1];
            n = capacity;
            count = 0;
        }
        public void insert(int data) {
            if (count >= n) return; // 堆满了
            ++count;
            a[count] = data;
            int i = count;
            while (i/2 > 0 && a[i] > a[i/2]) { // 自下往上堆化
                swap(a, i, i/2); // swap()函数作用：交换下标为i和i/2的两个元素
                i = i/2;
            }
        }
        private static void swap(int[] a, int i, int j) {
            int  temp = a[i];
            a[i] = a[j];
            a[j] = temp;
        }
        public static void main(String[] args) {
            int[] arr = {1,2,3,4};
            swap(arr,0,1);
            System.out.println();
        }
    }

从上往下