自己动手实现java数据结构（八） 优先级队列
|
上滤操作时，上滤元素进行比较的次数正比于上滤元素的深度。因此，上滤操作的时间复杂度为O(logN)。 @Override
insert(E newData) {
先插入新数据到 向量末尾
.innerArrayList.add(newData);
获得向量末尾元素下标
int lastIndex = getLastIndex();
对向量末尾元素进行上滤，以恢复堆序性
siftUp(lastIndex);
}
* 上滤操作
* index 需要上滤的元素下标
* void siftUp( index){
while(index >= 0 获得当前节点
int parentIndex = getParentIndex(index);
E currentData = .innerArrayList.get(index);
E parentData = .innerArrayList.get(parentIndex);
如果当前元素 大于 双亲元素
if(compare(currentData,parentData) > 0){
交换当前元素和双亲元素的位置
swap(index,parentIndex);
继续向上迭代
index = parentIndex;
}{
当前元素没有违反堆序性，直接返回
;
}
}
}
3.4 删除和下滤当优先级队列中极值元素出队时，需要在满足堆序性的前提下，选出新的极值元素。 我们简单的将当前向量末尾的元素放在堆顶，堆序性很有可能被破坏了。此时，我们需要对当前的堆顶元素进行一次下滤操作，使得整个完全二叉堆恢复堆序性。 下滤操作： 下滤的元素不断的和自己的左、右孩子节点进行优先级的比较： 1. 双亲节点最大，堆序性恢复，终止下滤。 2.?左孩子节点最大，当前下滤节点和自己的左孩子节点交换，继续下滤。 3.?右孩子节点最大，当前下滤节点和自己的右孩子节点交换，继续下滤。 4.?特别的，当下滤的元素抵达堆底时(成为叶子节点)，堆序性已经恢复，终止下滤。 下滤操作时间复杂度： 下滤操作时，下滤元素进行比较的次数正比于下滤元素的高度。因此，下滤操作的时间复杂度为O(logN)。 E popMax() {
.innerArrayList.isEmpty()){
throw new CollectionEmptyException("当前完全二叉堆为空");
}
将当前向量末尾的元素和堆顶元素交换位置
getLastIndex();
swap(0,lastIndex);
暂存被删除的最大元素（之前的堆顶最大元素被放到了向量末尾）
E max = .innerArrayList.get(lastIndex);
this.size-- 对当前堆顶元素进行下滤，以恢复堆序性
siftDown(0);
max;
}
* 下滤操作
* index 需要下滤的元素下标
* void siftDown(int size = .size();
叶子节点不需要下滤
int half = size >>> 1while(index < half){
int leftIndex = getLeftChildIndex(index);
int rightIndex = getRightChildIndex(index);
if(rightIndex < size){
右孩子存在 (下标没有越界)
E leftData = .innerArrayList.get(leftIndex);
E rightData = .innerArrayList.get(rightIndex);
E currentData = .innerArrayList.get(index);
比较左右孩子大小
if(compare(leftData,rightData) >= 0){
左孩子更大，比较双亲和左孩子
){
双亲最大，终止下滤
;
}{
三者中，左孩子更大，交换双亲和左孩子的位置
swap(index,leftIndex);
继续下滤操作
index = leftIndex;
}
}{
右孩子更大，比较双亲和右孩子
三者中，右孩子更大，交换双亲和右孩子的位置
rightIndex;
}
}
} 右孩子不存在 (下标越界)
.innerArrayList.get(leftIndex);
E currentData = 当前节点 大于 左孩子
终止下滤
;
} 交换 左孩子和双亲的位置
swap(index,leftIndex);
继续下滤操作
index = leftIndex;
}
}
}
}
3.5?批量元素建堆有时，我们需要将一个无序的元素集合数组转换成一个完全二叉堆，这一操作被称为批量建堆。 一个朴素的想法是：将无序集合中的元素依次插入一个空的完全二叉堆，对每一个新插入的元素进行上滤操作。使用上滤操作实现的对N个元素进行批量建堆的算法，其时间复杂度为O(n.logn)，比较直观。 但还存在一种效率更加高效的批量建堆算法，是以下滤操作为基础实现的，被称为Floyd建堆算法。下滤操作可以看做是将两个较小的堆合并为一个更大堆的过程(单个元素可以被视为一个最小的堆)，通过从底到高不断的下滤操作，原本无序的元素集合将通过不断的合并建立较小的堆，最终完成整个集合的建堆过程。 Floyd建堆算法的时间复杂度的证明较为复杂，其时间复杂度比起以上滤为基础的朴素算法效率高一个数量级，为O(n)。 （编辑：衡阳站长网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
