系列文章目录
数据结构之PriorityQueue源码及特性分析 (大小根堆转换、扩容)_crazy_xieyi的博客-CSDN博客
文章目录
前言
一、堆是什么?
堆的性质如下:
1.堆中某个节点的值总是不大于或不小于其父节点的值
2.堆总是一棵完全二叉树
二、堆的存储方式是什么?
从堆的概念可知,堆是一棵完全二叉树,因此可以层序的规则采用顺序的方式来高效存储。
注意:对于
非完全二叉树,则不适合使用顺序方式进行存储
,因为为了能够还原二叉树,
空间中必须要存储空节
点,就会导致空间利用率比较低
。
三、堆是怎么创建的?(大根堆)
1.
让
parent
标记需要调整的节点,
child
标记
parent
的左孩子
(
注意:
parent
如果有孩子一定先是有左孩子
)
2.
如果
parent
的左孩子存在,即
:child < usedsize
, 进行以下操作,直到
parent
的左孩子不存在。
parent
右孩子是否存在,存在找到左右孩子中最大的孩子
;
将
parent
与较大的孩子
child
比较,如果:
parent大
于较大的孩子
child
,调整结束
否则:交换
parent
与较大的孩子
child
,交换完成之后,
parent = child
;
child = parent*2+1;
然后继续
2
。
java"> public void createHeap(){
for (int parent = (usedSize-1-1)/2; parent >= 0 ; parent--) {
shiftDown(parent,usedSize);
}
}
/**
* 每个根节点向下调整
* @param parent 父节点
* @param usedSize 调整的结束位置不能超过
*/
public void shiftDown(int parent, int usedSize){
int child = parent*2 + 1;
while (child < usedSize){ //保证有左孩子
if(child+1 < usedSize && elem[child] < elem[child+1]){ //保证有右孩子且大于左孩子
child++;
}
if (elem[child] > elem[parent]){
int temp = elem[child];
elem[child] = elem[parent];
elem[parent] = temp;
parent = child;
child = parent*2 +1;
}else {
break;
}
}
}
四、建堆的时间复杂度是多少?O(n)
五、堆是怎么进行插入和删除元素的?
堆的插入总共需要两个步骤:
1. 先将元素放入到底层空间中(注意:空间不够时需要扩容)
2. 将最后新插入的节点向上调整,直到满足堆的性质
java">public void offer(int val){
if (isFull()){
elem = Arrays.copyOf(elem,2*elem.length);
}
elem[usedSize] = val;
usedSize++;
shiftUp(usedSize-1);
}
private void shiftUp(int child){
int parent = (child - 1)/2;
while (parent >= 0)
if (elem[child] > elem[parent]){
int temp = elem[parent];
elem[parent] = elem[child];
elem[child] = temp;
child = parent;
parent = (child - 1)/2;
}else {
break;
}
}
public boolean isFull(){
return elem.length == usedSize;
}
堆的删除一定删除的是堆顶元素。具体如下:
1. 将堆顶元素对堆中最后一个元素交换
2. 将堆中有效数据个数减少一个
3. 对堆顶元素进行向下调整
java"> public int pop(){
if (isEmpty()){
return -1;
}
int temp = elem[0];
elem[0] = elem[usedSize-1];
elem[usedSize-1] = temp;
usedSize--;
shiftDown(0,usedSize);
return temp;
}
public boolean isEmpty(){
return usedSize == 0;
}
/**
* 每个根节点向下调整
* @param parent 父节点
* @param usedSize 调整的结束位置不能超过
*/
public void shiftDown(int parent, int usedSize){
int child = parent*2 + 1;
while (child < usedSize){ //保证有左孩子
if(child+1 < usedSize && elem[child] < elem[child+1]){ //保证有右孩子且大于左孩子
child++;
}
if (elem[child] > elem[parent]){
int temp = elem[child];
elem[child] = elem[parent];
elem[parent] = temp;
parent = child;
child = parent*2 +1;
}else {
break;
}
}
}
六、用堆模拟实现优先级队列
java">public class MyPriorityQueue {
public int[] elem;
public int usedSize;
public MyPriorityQueue() {
this.elem = new int[11];
}
/**
* 建堆的时间复杂度:
*
* @param array
*/
public void createHeap(int[] array) {
for (int i = 0; i < array.length; i++) {
elem[i] = array[i];
usedSize++;
}
int parent = (usedSize-1-1)/2;
for (int i = parent; i >= 0; i--) {
shiftDown(parent,usedSize);
}
}
/**
*
* @param root 是每棵子树的根节点的下标
* @param len 是每棵子树调整结束的结束条件
* 向下调整的时间复杂度:O(logn)
*/
private void shiftDown(int root,int len) {
int child = root*2 + 1;
while (elem[child] > elem[root]){
if (child+1 < len && elem[child] < elem[child+1]){
child++;
}
if (elem[child] > elem[root]){
int temp = elem[child];
elem[child] = elem[root];
elem[root] = temp;
child = root;
root = (child-1)/2;
}else {
break;
}
}
}
/**
* 入队:仍然要保持是大根堆
* @param val
*/
public void push(int val) {
if (isFull()){
elem = Arrays.copyOf(elem,2*elem.length);
}
elem[usedSize] = val;
usedSize++;
shiftUp(usedSize-1);
}
private void shiftUp(int child) {
int parent = (child-1)/2;
while (parent >= 0){
if (elem[child] > elem[parent]){
int temp = elem[child];
elem[child] = elem[parent];
elem[parent] = temp;
child = parent;
parent = (child-1)/2;
}else {
break;
}
}
}
public boolean isFull() {
return usedSize == elem.length;
}
/**
* 出队【删除】:每次删除的都是优先级高的元素
* 仍然要保持是大根堆
*/
public void pollHeap() {
if (isEmpty()){
return;
}
int temp = elem[0];
elem[0] = elem[usedSize-1];
elem[usedSize-1] = temp;
usedSize--;
shiftDown(0,usedSize);
}
public boolean isEmpty() {
return usedSize == 0;
}
/**
* 获取堆顶元素
* @return
*/
public int peekHeap() {
if (isEmpty()){
System.out.println("队列为空!");
return -1;
}
return elem[0];
}
}