目录
1. 二叉树的顺序存储
1.1 存储方式
使用数组保存二叉树结构，方式即将二叉树用层序遍历方式放入数组中。
一般只适合表示完全二叉树，这种方式的主要用法就是堆的表示。
因为非完全二叉树会有空间的浪费（所有非完全二叉树用链式存储）。
编辑
1.2 下标关系
已知双亲(parent)的下标，则：
左孩子(left)下标 = 2 * parent + 1;
右孩子(right)下标 = 2 * parent + 2;
已知孩子（不区分左右）(child)下标，则：
双亲(parent)下标 = (child - 1) / 2;
2. 堆(heap)
2.1 概念
1. 堆逻辑上是一棵完全二叉树
2. 堆物理上是保存在数组中
3. 满足任意结点的值都大于其子树中结点的值，叫做大堆，或者大根堆，或者最大堆
4. 反之，则是小堆，或者小根堆，或者最小堆
5. 堆的基本作用是，快速找集合中的最值
2.2 操作-（下沉&上浮）本例是最大堆
元素下沉：
/** * 下沉操作 */ public void siftDown(int k){ //还存在子树 while (leftChild(k) < data.size()){ int j = leftChild(k); //判断是否存在右子树且大于左子树的值 if(j+1 < data.size() && data.get(j+1) > data.get(j)){ j=j+1; } //此时j为左右子树最大值 //和当前节点比较大小 if(data.get(j) <= data.get(k)){ break; }else { swap(k,j); k=j; } } }
元素上浮：
/** * 上浮操作 */ // 上浮操作的终止条件: 已经走到根节点 || 当前节点值 <= 父节点值 // 循环的迭代条件 : 还存在父节点并且当前节点值 > 父节点值 private void siftUp(int k) { while (k>0 && data.get(k)>data.get(parent(k))){ swap(k,parent(k)); k=parent(k); } }
其中swap方法是交换操作：
//交换三连 private void swap(int i,int j) { int temp = data.get(j); data.set(j,data.get(i)); data.set(i,temp); }
堆化数组：
/** * 将任意数组堆化 * @param arr */ public MaxHeap(int[] arr){ data = new ArrayList<>(arr.length); // 1.先将arr的所有元素复制到data数组中 for(int i : arr){ data.add(i); } // 2.从最后一个非叶子结点开始进行siftDown for (int i = parent(data.size()-1); i >=0 ; i--) { siftDown(i); } }
图示：
以此数组为例：
// 调整前 int[] array = { 27,15,19,18,28,34,65,49,25,37 }; // 调整后 int[] array = { 15,18,19,25,28,34,65,49,27,37 };
编辑
时间复杂度分析：
最坏的情况即图示的情况，从根一路比较到叶子，比较的次数为完全二叉树的高度
即时间复杂度为O(log(n))
2.3 建堆-完整代码（最大堆）
/** * 基于整形最大堆实现 * 时根节点从0开始编号,若此时节点编号为k * 左孩子为2k+1 * 右孩子为2k+2 * 父节点为（k-1）/2 */ import java.util.ArrayList; import java.util.List; import java.util.NoSuchElementException; public class MaxHeap { // 使用JDK的动态数组(ArrayList)来存储一个最大堆 List<Integer> data; // 构造方法的this调用 public MaxHeap(){ this(10); } // 初始化的堆大小 public MaxHeap(int size){ data = new ArrayList<>(size); } /** * 将任意数组堆化 * @param arr */ public MaxHeap(int[] arr){ data = new ArrayList<>(arr.length); // 1.先将arr的所有元素复制到data数组中 for(int i : arr){ data.add(i); } // 2.从最后一个非叶子结点开始进行siftDown for (int i = parent(data.size()-1); i >=0 ; i--) { siftDown(i); } } /** * 向最大堆中增加值为Value的元素 * @param value */ public void add(int value){ //1.先直接加到堆的末尾 data.add(value); //2.元素上浮操作 siftUp(data.size()-1); } /** * 只找到堆顶元素值 * @return */ public int peekMax (){ if(isEmpty()){ throw new NoSuchElementException("heap is empty!connot peek"); } return data.get(0); } /** * 取出当前最大堆的最大值 */ public int extractMax(){ // 取值一定注意判空 if(isEmpty()){ throw new NoSuchElementException("heap is empty!connot extract"); } int max = data.get(0); // 1.将数组末尾元素顶到堆顶 int lastValue =data.get(data.size()-1); data.set(0,lastValue); // 2.将数组末尾的元素删除 data.remove(data.size()-1); // 3.进行元素的下沉操作 siftDown(0); return max; } /** * 下沉操作 */ public void siftDown(int k){ //还存在子树 while (leftChild(k) < data.size()){ int j = leftChild(k); //判断是否存在右子树且大于左子树的值 if(j+1 < data.size() && data.get(j+1) > data.get(j)){ j=j+1; } //此时j为左右子树最大值 //和当前节点比较大小 if(data.get(j) <= data.get(k)){ break; }else { swap(k,j); k=j; } } } /** * 上浮操作 */ // 上浮操作的终止条件: 已经走到根节点 || 当前节点值 <= 父节点值 // 循环的迭代条件 : 还存在父节点并且当前节点值 > 父节点值 private void siftUp(int k) { while (k>0 && data.get(k)>data.get(parent(k))){ swap(k,parent(k)); k=parent(k); } } //交换三连 private void swap(int i,int j) { int temp = data.get(j); data.set(j,data.get(i)); data.set(i,temp); } //判读堆为空 public boolean isEmpty(){ return data.size() == 0; } //根据索引找父节点 public int parent(int k){ return (k-1)>>1; } //根据索引找左孩子 public int leftChild(int k){ return k<<2+1; } //根据索引找右孩子 public int rightChild(int k){ return k<<2+2; } @Override public String toString() { return data.toString(); } }
ps:随机数操作
int[] data=new int[10000]; //随机数 ThreadLocalRandom random = ThreadLocalRandom.current(); for (int i = 0; i < data.length; i++) { data[i] = random.nextInt(); }
3. 优先级队列
详见下节：《Java 堆 & 优先级队列（下）》
