1.是一棵完全二叉树
满二叉树：1.除叶子节点之处的所有节点都有左右子树
2.叶子节点都在最后一层
3.每一层节点的个数：2^（layer-1) layer代表层数
4.叶子节点的个数：2^（h-1） h 代表树的高度
5.非叶子节点的个数：2^（h-1）-1
6.节点的个数：2^h-1
完全二叉树：按照树的结构，从左到右依次排列，把元素排列成树的形状
优先队列：普通队列： 先进先出
优先队列：出队顺序和入队顺序无关，和优先级有关。当访问元素时，优先级最高的会被删除。可以使用堆这种数 据结构作为优先队列的底层结构
（最大）堆是一个可以被看成一棵树的数组对象，满足如下性质:
a. 堆中的父亲结点总大于或等于其左右孩子结点的值
b.总是一棵完全二叉树
根据堆的性质可以得出如下结论 ：1> 根节点没有父亲结点
2>除根节点之外的任意结点（i）的父亲结点的索引为： parent = i/2
3>任意结点的左孩子结点的索引为: leftIndex = 2 * i
4>任意结点的右孩子结点的索引为： rightIndex = 2 * i +1
上面的结论是根结点存储在索引为1的位置，如果根结点存储在索引为0的位置时，会得到：
parent = (i- 1)/2;
leftIndex = 2 * i + 1
rightIndex = 2 * I + 2
构建堆：public class MaxHeap向堆中添加元素> { private T[] data; // 保存堆中的数据 private int size;// 堆中元素的个数 public MaxHeap() { this.size = 0; this.data = (T[]) new Comparable[200]; } public MaxHeap(T[] arr) { this.data = Arrays.copyOf(arr, arr.length); this.size = arr.length; } // 获取优先级最高的元素 public T getPriorityFirst() { return isEmpty() ? null : this.data[0]; } // 判断最大堆是否为空 public boolean isEmpty() { return this.size == 0; } // 获取堆中元素的个数 public int getSize() { return this.size; } //获取左孩子的索引，由于是完全二叉树，因此右孩子的索引为做孩子加一 private int getLeftChildIndex(int index) { if (index < 0) { throw new IllegalArgumentException("index is invalid!"); } return 2 * index + 1; } //获取父亲节点的索引 private int getParentIndex(int index) { if (index < 0) { throw new IllegalArgumentException("index is invalid!"); } else if (index == 0) { return -1; } else { return (index - 1) / 2; } } //重写tospring来方便测试 @Override public String toString() { StringBuilder sb = new StringBuilder("["); int i = 0; while (i < size) { sb.append(this.data[i]); if (i != size - 1) { sb.append(","); } i++; } sb.append("]"); return sb.toString(); } }
由于我们创建的堆为最大堆，是一棵完全二叉树，因此每次添加都是在末尾添加，使用浮动 *** 作
// 添加 *** 作
public void add(T ele) {
// 1、保存数据
data[this.size] = ele;
//2、更新size
size += 1;
//3、浮动 *** 作
floatUp(size - 1);
// floatUp2(ele);
}
// 浮动 *** 作方式一：
private void floatUp(int i) {
int curIndex = i;//防止我们拿过来的i值改变，因此定义一个curIndex（当前节点）的值等于i
// 1、获取父亲节点的索引
int parentIndex = getParentIndex(curIndex);
// 2、比较优先级，如果比父亲节点的优先级高，就交换
while (curIndex > 0 && data[curIndex].compareTo(data[parentIndex]) > 0) {
//交换 *** 作，交换当前节点和父亲节点（父亲节点值大为前提）
swap(this.data, curIndex, parentIndex);
//交换 *** 作交换的为值，现在改变当前节点和父亲节点的索引
curIndex = parentIndex;
parentIndex = getParentIndex(curIndex);
}
}
// 浮动 *** 作
private void floatUp2(T ele) {
// 1、获取父亲节点的索引
int curIndex = this.size - 1;
int parentIndex = getParentIndex(curIndex);
// 2、比较优先级，如果比父亲节点的优先级高，就交换
while (curIndex > 0 && ele.compareTo(data[parentIndex]) > 0) {
//值交换
data[curIndex] = data[parentIndex];
//索引交换
curIndex = parentIndex;
parentIndex = getParentIndex(curIndex);
}
//值交换
data[curIndex] = ele;
}
//交换 *** 作
private void swap(T[] arr, int curIndex, int changeIndex) {
T temp = arr[curIndex];
arr[curIndex] = arr[changeIndex];
arr[changeIndex] = temp;
}
//测试
public static void main(String[] args) {
Random random = new Random();//随机数
MaxHeap heap = new MaxHeap<>();
for (int i = 0; i < 7; i++) {
heap.add(random.nextInt(50));
}
System.out.println(heap);
heap.add(51);
System.out.println(heap);
}
取出堆中优先级最高的元素（下沉 swim）
注意：最大堆中优先级最高的元素是索引为0的元素
先取出根节点，把堆中最后一个元素放到跟节点，进行下沉 *** 作。
下沉 *** 作:跟元素（堆末尾元素）和左右孩子比较，若比左右孩子小，做交换，放到优先级高的那个孩子上，
//下沉 *** 作方式一：
private void swim() {
if (isEmpty()) {//判断是否为空
return;
}
int curIndex = 0;
//上文定义的方法，获取当前节点左孩子的索引
int leftIndex = getLeftChildIndex(curIndex);
int changeIndex = leftIndex;// 保存左右孩子优先级高的索引，假设优先级高的暂时为左孩子
// 有左孩子的条件： leftIndex < this.size;rightIndex < this.size
while (leftIndex < this.size) {
//左右孩子小于size，左孩子的值<右孩子的值执行while
if (leftIndex + 1 < this.size && data[leftIndex].compareTo(data[leftIndex + 1]) < 0) {
//优先级高的为右孩子，否则，直接用上文定义的int changeIndex = leftIndex;
changeIndex = leftIndex + 1;
}
//当前节点值大于优先级高的孩子，则不做变化
if (data[curIndex].compareTo(data[changeIndex]) > 0) {
break;
}
//交换值 *** 作
swap(this.data, curIndex, changeIndex);
//交换索引的 *** 作
curIndex = changeIndex;
leftIndex = getLeftChildIndex(curIndex);
changeIndex = leftIndex;
}
}
// 下沉 *** 作方式二：
private void swim2() {
if (isEmpty()) {
return;
}
T rootEle = this.data[0];
int curIndex = 0;
int leftIndex = getLeftChildIndex(curIndex);
int changeIndex = leftIndex;// 保存左右孩子优先级高的索引
// 有左孩子的条件： leftIndex < this.size
while (leftIndex < this.size) {
//左右孩子小于size，左孩子的值<右孩子的值执行while
if (leftIndex + 1 < this.size && data[leftIndex].compareTo(data[leftIndex + 1]) < 0) {
//优先级高的为右孩子，否则，直接用上文定义的int changeIndex = leftIndex;
changeIndex = leftIndex + 1;
}
//当前节点值大于优先级高的孩子，则不做变化
if (rootEle.compareTo(data[changeIndex]) > 0) {
break;
}
//交换值 *** 作
data[curIndex] = data[changeIndex];
//交换索引的 *** 作
curIndex = changeIndex;
leftIndex = getLeftChildIndex(curIndex);
changeIndex = leftIndex;
}
//交换值 *** 作
data[curIndex] = rootEle;
}
//测试
public static void main(String[] args) {
Random random = new Random();
MaxHeap heap = new MaxHeap<>();
for (int i = 0; i < 7; i++) {
heap.add(random.nextInt(50));
}
int max = heap.removePriorityFirst();
System.out.println(max);
System.out.println(heap)
}
堆的时间复杂度分析
无论进行上浮还是下沉 *** 作，最多交换的次数为整棵树的高度h
O(h) = O(logn)
堆排序从最大堆中依次取出元素（从上到下，从左到右）
public void sort(T[] arr) {
if (arr == null || arr.length == 0) {
return;
}
// 构建堆
Arrays.stream(arr).forEach(item -> this.add(item));//流遍历
// 依次删除根节点
int index = 0;
while (!isEmpty()) {
arr[index++] = this.removePriorityFirst();
}
}
//测试
public static void main(String[] args) {
Random random = new Random();
Integer[] arr = new Integer[12];
for (int i = 0; i < arr.length; i++) {
arr[i] = random.nextInt(50);
}
Maxheap heap = new Maxheap<>();
heap.sort(arr);
System.out.println(Arrays.toString(arr));
}
Heapify和Replace
replace： 取出最大元素后，放入一个新元素
实现方式：直接将堆顶元素替换成新元素，然后进行Sift down *** 作
heapify: 将任意数组整理成堆的形状
实现方式：从最后一个元素的父亲结点开始进行调整（sift down），直到根结点
Replace实现:
// replace *** 作:取出优先级最高的元素，放入一个新元素---（让新元素替换索引为0的元素）
public void replace(T newEle) {
this.data[0] = newEle;
swim2();
}
Heapify实现：
1、找到最后一个元素的父亲结点。 (size-1-1)/2
2、循环进行下沉 *** 作，直至根结点
//heapify *** 作:将任意数组整理成堆
//方式一：一次添加
public void heapify() {
if (this.data == null || this.data.length == 0) {
return;
}
//获得最后一个元素的父亲节点
int lastEleParentIndex = (this.data.length - 1 - 1) / 2;
for (; lastEleParentIndex >= 0; lastEleParentIndex--) {
heapifyswim(this.data, lastEleParentIndex, this.data.length);
}
}
//方式二：
private void heapifyswim(T[] arr, int lastEleParentIndex, int length) {
int curIndex = lastEleParentIndex;
int leftIndex = getleftchildindex(curIndex);
int changeIndex = leftIndex;
while (leftIndex < length) {
if (leftIndex + 1 < length && arr[leftIndex].compareTo(arr[leftIndex + 1]) < 0) {
changeIndex = leftIndex + 1;
}
if (arr[curIndex].compareTo(arr[changeIndex]) > 0) {
break;
}
swap(arr, curIndex, changeIndex);
curIndex = changeIndex;
leftIndex = getleftchildindex(curIndex);
changeIndex = leftIndex;
}
}
Heapify复杂度分析
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）