甘肃今天疫情最新情况_seo公司 彼亿营销_成都本地推广平台_厦门百度关键词推广

1.弗洛伊德建堆算法

Floyd 建堆算法作者（也是之前龟兔赛跑判环作者）：

1. 找到最后一个非叶子节点
2. 从后向前，对每个节点执行下潜

一些规律

• 一棵满二叉树节点个数为 $2^h-1$，如下例中高度 $h=3$ 节点数是 $2^3-1=7$
• 非叶子节点范围为 $[0,size/2-1]$

算法时间复杂度分析

下面看交换次数的推导：设节点高度为 3

	本层节点数	高度	下潜最多交换次数（高度-1）
4567 这层	4	1	0
23这层	2	2	1
1这层	1	3	2

推导出
$$2^h-h-1$$
其中 $2^h\approx n$，$h\approx {\log }_{2}n$，因此有时间复杂度 $O(n)$

public class MaxHeap {private int[] array;private int size;public MaxHeap() {this.array = new int[32];}public MaxHeap(int capacity) {this.array = new int[capacity];}public MaxHeap(int[] array) {this.array = array;this.size = array.length;heapify();//建堆操作}/*** 建堆方法* 1.找到最后一个非叶子节点* 2.从后向前，对每个节点执行下潜*/private void heapify() {//1.找最后一个非叶子节点，公式为：floor((i - 1)/2),i是索引，所以要减2int node = (size - 2) / 2;for (int i = node; i >= 0; i--) {down(i);}}//删除堆顶元素public int poll() {return poll(0);}//根据索引删除元素public int poll(int index) {if(isEmpty()){throw new IllegalArgumentException("数组数据异常");}swap(index, size - 1);int value = array[--size];down(index);return value;}//替换堆顶元素public void replace(int value) {if(isEmpty()){throw new IllegalArgumentException("数组数据异常");}array[0] = value;down(0);}//获取堆顶元素public int peek() {if(isEmpty()){throw new IllegalArgumentException("数组数据异常");}return array[0];}//堆尾部添加元素public boolean offer(int value) {if(isFull()){return false;}array[size] = value;up(size);size++;return true;}//下潜private void down(int parent) {//1.把父节点和两个孩子中较大的比较int left = 2 * parent + 1;int right = 2 * parent + 2;int max = parent;if (left < size && array[left] > array[max]) {max = left;}if (right < size && array[right] > array[max]) {max = right;}if (max != parent) {//找到的更大的孩子swap(max, parent);down(max);}}//上浮private void up(int child) {//子节点和父节点进行比较int parent = (child - 1) / 2;while (parent >= 0 && array[parent] < array[child]) {swap(parent, child);child = parent;parent = (child - 1) / 2;}}//交换private void swap(int i, int j) {int temp = array[i];array[i] = array[j];array[j] = temp;}private boolean isEmpty(){return size == 0;}private boolean isFull(){return size == array.length;}
}

堆排序

算法描述

1. heapify 建立大顶堆
2. 将堆顶与堆底交换（最大元素被交换到堆底），缩小并下潜调整堆
3. 重复第二步直至堆里剩一个元素

public static void main(String[] args) {int[] arr = new int[]{2, 1, 4, 5, 6, 9, 7, 8};MaxHeap heap = new MaxHeap(arr);while (heap.size > 1){heap.swap(0, heap.size - 1);heap.size--;heap.down(0);}System.out.println(Arrays.toString(heap.array));
}

LeetCode题目

215题
703题
295题