扁平化的网站有哪些,八大员继续教育入口,卖汽车的网站怎么做的吗,手机免费建立网站目录
1.概念
2.表示
3.三大操作
4.代码实现最大堆#xff08;基于数组#xff0c;编号从0开始#xff09;
4.1.根据孩子节点k获取当前父节点的索引
4.2.根据父节点k求左孩子节点下标
4.3.根据父节点k求右孩子节点下标
4.4.判空
4.5.toString()方法
4.6.判断数组中…目录
1.概念
2.表示
3.三大操作
4.代码实现最大堆基于数组编号从0开始
4.1.根据孩子节点k获取当前父节点的索引
4.2.根据父节点k求左孩子节点下标
4.3.根据父节点k求右孩子节点下标
4.4.判空
4.5.toString()方法
4.6.判断数组中元素是否有序
4.7.查看堆顶元素
4.8.交换当前数组中 i 和 parent 的值
4.9.将value存储在堆中
4.10.元素上浮操作
4.11.取出当前堆的最大值继续调整堆
4.12.元素下沉操作
4.13.heapify堆化操作将任意给定的整型数组调整为堆
4.14.测试
5.总代码实现
6.总结 1.概念
逻辑上是一棵完全二叉树物理上是保存在数组中。基于二叉树的堆叫二叉堆。堆的实现基本都是二叉树还有其他的少从节点值的要求来看分为
最大堆Java中的叫法/大根堆C中的叫法堆中根节点的值 左右子树节点值。最小堆/小根堆JDK优先级队列就是小根堆堆中根节点的值 左右子树节点值。左右子树仍满足此性质。
注
最大/小堆的节点大小关系与节点高度无关相同的数据下可能有不同种类的堆例可有最大堆构建也可有最小堆构建。二分搜索树比堆的节点值大小关系要求更严格。2.表示
用数组表示动态数组可扩容编号表示结构。2种
① ② 3.三大操作
add向堆末尾添加元素。PSsiftUp元素上浮。extractMax取出当前堆的最大值元素。PSsiftDown元素下沉。heapify堆化将任意给定的整型数组调整为堆。PSsiftDown元素下沉。
4.代码实现最大堆基于数组编号从0开始
4.1.根据孩子节点k获取当前父节点的索引
/*** 根据孩子节点k获取当前父节点的索引* param k* return*/
private int parent(int k) {return (k - 1) 1; //位运算符比除法要快 return (k - 1) / 2;
}
4.2.根据父节点k求左孩子节点下标
/*** 根据父节点k求左孩子节点下标* param k* return*/
private int leftChild(int k) {return ( k 1 ) 1; //2k 1
}
4.3.根据父节点k求右孩子节点下标
/*** 根据父节点k求右孩子节点下标* param k* return*/
private int rightChild(int k) {return (k 1) 2; //2k 2
}
4.4.判空
/*** 判空* return*/
public boolean isEmpty() {return data.size() 0;
}
4.5.toString()方法
Override
public String toString() {StringBuilder sb new StringBuilder();sb.append([);for (int i 0; i data.size(); i) {sb.append(data.get(i));if(i ! data.size() - 1){sb.append(,);}}sb.append(]);return sb.toString();
}
Override
public String toString() {return data.toString();
}
4.6.判断数组中元素是否有序
/*** 判断数组中元素是否有序* param arr* return*/
public static boolean isSorted(int[] arr) {for (int i 0; i arr.length - 1; i) { //i arr.length - 1走不到最后一个元素arr.length - 1是最后一个元素if(arr[i] arr[i 1]) {return false;}}return true;
}
4.7.查看堆顶元素
/*** 查看堆顶元素* return*/
public int peekHeap() {if(data.size() 0) {throw new NoSuchElementException(heap is empty!);}return data.get(0);
}
4.8.交换当前数组中 i 和 parent 的值
/*** 交换当前数组中 i 和 parent 的值* param i* param parent*/
private void swap(int i, int parent) {int tmp data.get(i);int parentVal data.get(parent);data.set(i,parentVal);data.set(parent,tmp);
}
4.9.将value存储在堆中
/*** 将value存储在堆中* param value*/
public void add(int value) {//1.向数组末尾添加元素this.data.add(value);//2.调整当前堆的结构使其仍然满足最大堆的性质siftUp(data.size() - 1);
}
4.10.元素上浮操作
/*** 元素上浮操作* param i 要上浮的元素索引*/
private void siftUp(int i) {while(i 0 data.get(i) data.get(parent(i))) {swap(i,parent(i));//继续向上判断交换后父节点向上的节点关系i parent(i);}
}
4.11.取出当前堆的最大值继续调整堆
/*** 取出当前堆的最大值继续调整堆* return*/
public int extractMax() {//判断当前堆是否为空if(data.size() 0) {throw new NoSuchElementException(heap is empty!);}int max data.get(0);//将最后一个元素顶到堆顶int lastElement data.get(data.size() - 1);data.set(0, lastElement);//删除最后一个元素data.remove(data.size() - 1);//元素下沉siftDown(0);return max;
}
4.12.元素下沉操作
/*** 元素下沉操作* param i 要下沉的元素索引*/
private void siftDown(int i) {//终止条件当i还有子树时说明还没判断结束若左孩子都不存在则一定不存在右孩子while(leftChild(i) data.size()) {//此时i索引对应的元素仍然存在左子树没到叶子节点int j leftChild(i);//此时还存在右子树if(j 1 data.size() data.get(j 1 ) data.get(j)) {//此时右子树的值大于左子树j j 1;}//j一定保存了左右子树的最大值索引if(data.get(i) data.get(j)) { //此处为何是 //如果此处终止条件是 父节点 子节点也可以不会死循环//以后在写测试用例时必须要复杂//此时i对应的元素已经下沉到合适位置break;}else{swap(i,j);i j;}}
}
4.13.heapify堆化操作将任意给定的整型数组调整为堆
/*** heapify堆化操作将任意给定的整型数组调整为堆* ①自底向上逐渐调整堆的过程只看非叶子节点从最后一个非叶子节点最后一个非叶子节点就是最后一个节点他爸开始一次性砍掉所有叶子节点进行元素的siftDown操作直到向上走到根节点即可时间复杂度为O(n)* ②遍历原数组依次add操作时间复杂度为O(nlogn)* param arr*/
public MaxHeap(int[] arr) {//初始化data new ArrayList(arr.length);//1.先将arr的所有元素拷贝到data中for(int i : arr) {data.add(i);}//2.从最后一个非叶子节点开始进行元素下沉for (int i parent(data.size() - 1); i 0 ; i--) {siftDown(i);}
}
4.14.测试
public static void main(String[] args) {
// MaxHeap heap new MaxHeap();
// heap.add(5);
// heap.add(2);
// heap.add(7);
// heap.add(1);
// heap.add(3);
// System.out.println(heap);
//
// int[] ret new int[5];
// for (int i 0; i ret.length; i) {
// ret[i] heap.extractMax();
// }
// System.out.println(Arrays.toString(ret));// int[] data {17,90,68,12,15,14,70,30,20};
// MaxHeap heap new MaxHeap(data.length);
// //依次调用extractMax()-集合恰好是一个降序集合
// for (int i 0; i data.length; i) {
// heap.add(data[i]);
// }
// for (int i 0; i data.length; i) {
// data[i] heap.extractMax();
// }
// System.out.println(Arrays.toString(data));// int[] data {17,90,68,12,15,14,70,30,20};
// MaxHeap heap new MaxHeap(data);
// //依次调用extractMax()-集合恰好是一个降序集合
// for (int i 0; i data.length; i) {
// data[i] heap.extractMax();
// }
// System.out.println(Arrays.toString(data));int n 10000;int[] data new int[n];//生成随机数Random random new Random();for (int i 0; i n; i) {//范围是 0 - Integer.MAX_VALUEdata[i] random.nextInt(Integer.MAX_VALUE);}MaxHeap heap new MaxHeap(data);for (int i 0; i n; i) {data[i] heap.extractMax();}System.out.println(isSorted(data));
}
5.总代码实现
import java.util.*;/*** 基于数组实现的最大堆* 编号从0开始假设当前节点为i,i0* parent (i - 1) / 2;* 若有左右孩子保证 2i 1 或 2i 2 data.length;* left 2i 1;* right 2i 2;*/
public class MaxHeap {//具体存储元素的动态数组private ListInteger data;//无参构造public MaxHeap() {this(10);}//指定容量大小public MaxHeap(int initCap) {this.data new ArrayList(initCap);}/*** 根据孩子节点k获取当前父节点的索引* param k* return*/private int parent(int k) {return (k - 1) 1; //位运算符比除法要快 return (k - 1) / 2;}/*** 根据父节点k求左孩子节点下标* param k* return*/private int leftChild(int k) {return ( k 1 ) 1; //2k 1}/*** 根据父节点k求右孩子节点下标* param k* return*/private int rightChild(int k) {return (k 1) 2; //2k 2}/*** 判空* return*/public boolean isEmpty() {return data.size() 0;}Overridepublic String toString() {return data.toString();}/*** 判断数组中元素是否有序* param arr* return*/public static boolean isSorted(int[] arr) {for (int i 0; i arr.length - 1; i) { //i arr.length - 1走不到最后一个元素arr.length - 1是最后一个元素if(arr[i] arr[i 1]) {return false;}}return true;}/*** 查看堆顶元素* return*/public int peekHeap() {if(data.size() 0) {throw new NoSuchElementException(heap is empty!);}return data.get(0);}/*** 交换当前数组中 i 和 parent 的值* param i* param parent*/private void swap(int i, int parent) {int tmp data.get(i);int parentVal data.get(parent);data.set(i,parentVal);data.set(parent,tmp);}/*** 将value存储在堆中* param value*/public void add(int value) {//1.向数组末尾添加元素this.data.add(value);//2.调整当前堆的结构使其仍然满足最大堆的性质siftUp(data.size() - 1);}/*** 元素上浮操作* param i 要上浮的元素索引*/private void siftUp(int i) {while(i 0 data.get(i) data.get(parent(i))) {swap(i,parent(i));//继续向上判断交换后父节点向上的节点关系i parent(i);}}/*** 取出当前堆的最大值继续调整堆* return*/public int extractMax() {//判断当前堆是否为空if(data.size() 0) {throw new NoSuchElementException(heap is empty!);}int max data.get(0);//将最后一个元素顶到堆顶int lastElement data.get(data.size() - 1);data.set(0, lastElement);//删除最后一个元素data.remove(data.size() - 1);//元素下沉siftDown(0);return max;}/*** 元素下沉操作* param i 要下沉的元素索引*/private void siftDown(int i) {//终止条件当i还有子树时说明还没判断结束若左孩子都不存在则一定不存在右孩子while(leftChild(i) data.size()) {//此时i索引对应的元素仍然存在左子树没到叶子节点int j leftChild(i);//此时还存在右子树if(j 1 data.size() data.get(j 1 ) data.get(j)) {//此时右子树的值大于左子树j j 1;}//j一定保存了左右子树的最大值索引if(data.get(i) data.get(j)) { //此处为何是 //如果此处终止条件是 父节点 子节点也可以不会死循环//以后在写测试用例时必须要复杂//此时i对应的元素已经下沉到合适位置break;}else{swap(i,j);i j;}}}/*** heapify堆化操作将任意给定的整型数组调整为堆* ①自底向上逐渐调整堆的过程只看非叶子节点从最后一个非叶子节点最后一个非叶子节点就是最后一个节点他爸开始一次性砍掉所有叶子节点进行元素的siftDown操作直到向上走到根节点即可时间复杂度为O(n)* ②遍历原数组依次add操作时间复杂度为O(nlogn)* param arr*/public MaxHeap(int[] arr) {//初始化data new ArrayList(arr.length);//1.先将arr的所有元素拷贝到data中for(int i : arr) {data.add(i);}//2.从最后一个非叶子节点开始进行元素下沉for (int i parent(data.size() - 1); i 0 ; i--) {siftDown(i);}}public static void main(String[] args) {
// MaxHeap heap new MaxHeap();
// heap.add(5);
// heap.add(2);
// heap.add(7);
// heap.add(1);
// heap.add(3);
// System.out.println(heap);
//
// int[] ret new int[5];
// for (int i 0; i ret.length; i) {
// ret[i] heap.extractMax();
// }
// System.out.println(Arrays.toString(ret));// int[] data {17,90,68,12,15,14,70,30,20};
// MaxHeap heap new MaxHeap(data.length);
// //依次调用extractMax()-集合恰好是一个降序集合
// for (int i 0; i data.length; i) {
// heap.add(data[i]);
// }
// for (int i 0; i data.length; i) {
// data[i] heap.extractMax();
// }
// System.out.println(Arrays.toString(data));// int[] data {17,90,68,12,15,14,70,30,20};
// MaxHeap heap new MaxHeap(data);
// //依次调用extractMax()-集合恰好是一个降序集合
// for (int i 0; i data.length; i) {
// data[i] heap.extractMax();
// }
// System.out.println(Arrays.toString(data));int n 10000;int[] data new int[n];//生成随机数Random random new Random();for (int i 0; i n; i) {//范围是 0 - Integer.MAX_VALUEdata[i] random.nextInt(Integer.MAX_VALUE);}MaxHeap heap new MaxHeap(data);for (int i 0; i n; i) {data[i] heap.extractMax();}System.out.println(isSorted(data));}
}
6.总结
将任意数组调整为堆而后依次extractMax的操作得到的就是一个排序数组——时间复杂度O(nlogn)。
需要开辟一个和原数组大小完全相同的临时空间——空间复杂度O(n)。
优化原地堆排序。
