2023.03.09

1.手写堆，heapify，heapinsert，insert，isempty，delete
2.给定一个大致有序的数组且交换k步之内必变，写一个时间复杂度合适的算法，利用堆排序，因为是k步之内必有序，设置一个小根堆，堆的大小是k+1，每次弹出堆顶，弹出是再进一个元素，堆弹完，排序完成
3.给定一组线段，线段给起始和终点位置，要求找到线段最密集的区间的线段条数。利用堆的特点，先将start用堆排好序，按照排好序的start一次进堆，start进堆时，堆弹出所有比start小的数，end进堆，统计堆内元素个数。遍历完start数组后，取最大的元素个数。即是答案。这题需要手写堆，手写堆让火车撞了都不能忘。
4.堆排序的时间复杂度为n的优化，数组从后往前做heapify，也就是从最右边叶节点开始，所有节点做heapify的个数加在一起，利用错位相减与等比数列，得出时间复杂度收敛于n