二叉堆实现
2023-07-05 本文已影响0人
小陈wx
二叉堆-快速查找
# # 一个维护起来的二叉堆（小顶堆/大顶堆）在查询最大值/最小值时，时间复杂度为O(1)
# # 插入的时间复杂度为O(logn)
# # 删除的时间复杂度为O(logn)
# # 适用于频繁更新的数据中查找最大值/最小值，例如A星寻路算法找最小成本，股票交易系统中找最大利润，工厂库存管理中找最小库存等
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>Document</title>
</head>
<body>
<h1>二叉堆-快速查找</h1>
<h3>
一个维护起来的二叉堆（小顶堆/大顶堆）在查询最大值/最小值时，时间复杂度为O(1)
<br/>插入的时间复杂度为O(logn)
<br/>删除的时间复杂度为O(logn)
<br/>适用于频繁更新的数据中查找最大值/最小值，例如A星寻路算法找最小成本，股票交易系统中找最大利润，工厂库存管理中找最小库存等
</h3>
<div id="arr"></div>
<button onclick="getMin()">获取最小值</button>
<div id="min">--</div>
<button onclick="getMax()">获取最大值</button>
<div id="max">--</div>
</body>
<script>
var bh = null;
var arr = []
for(var i = 0; i < 1000; i++){
arr.push(Math.random() * 1000);
}
document.getElementById("arr").innerHTML = arr.join(",");
var bh_max = testHeapSort(arr,"max");
var bh_min = testHeapSort(arr,"min");
function getMin(){
var val = bh_min.peek();
document.getElementById("min").innerHTML = val;
}
function getMax(){
var val = bh_max.peek();
document.getElementById("max").innerHTML = val;
}
function testHeapSort(arr,type){
var bh = new BinaryHeap(type);
for(var i = 0; i < arr.length; i++){
bh.insert(arr[i]);
}
return bh;
}
//创建一个二叉堆类
function BinaryHeap(tpye="min"){
//堆的类型，最大堆或最小堆
this.type = tpye;
//建立二叉堆
this.heap = [];
//插入节点
this.insert = function(value){
this.heap.push(value);
this.shiftUp(this.heap.length - 1);
}
//删除堆顶
this.pop = function(){
//将堆顶元素与最后一个元素交换
this.swap(0, this.heap.length - 1);
//删除最后一个元素（原来的堆顶）
var res = this.heap.pop();
//将新的堆顶元素下沉
this.shiftDown(0);
return res;
}
//交换堆中两个元素
this.swap = function(i1, i2){
var temp = this.heap[i1];
this.heap[i1] = this.heap[i2];
this.heap[i2] = temp;
}
//获取堆顶
this.peek = function(){
return this.heap[0];
}
//获取堆大小
this.size = function(){
return this.heap.length;
}
//寻找父节点
this.getParentIndex = function(index){
return Math.floor((index - 1) / 2);
}
//判断是否为叶节点
this.isLeaf = function(index){
return index >= Math.floor(this.heap.length / 2) && index <= this.heap.length - 1;
}
//上浮调整
this.shiftUp = function(index){
if(index == 0) return;
//找到父节点
var parentIndex = this.getParentIndex(index);
//根据大小堆则交换
if(this.type == "max"){
if(this.heap[parentIndex] < this.heap[index]){
this.swap(parentIndex, index);
this.shiftUp(parentIndex);
}
}else{
if(this.heap[parentIndex] > this.heap[index]){
this.swap(parentIndex, index);
this.shiftUp(parentIndex);
}
}
}
//下沉调整
this.shiftDown = function(index){
//找到左右子节点的索引
var leftIndex = this.getLeftIndex(index);
var rightIndex = this.getRightIndex(index);
//如果左子节点不存在，则不需要下沉
if(this.heap[leftIndex] == undefined) return;
//如果右子节点不存在，则比较左子节点
if(this.heap[rightIndex] == undefined){
if(this.type == "max"){
if(this.heap[leftIndex] > this.heap[index]){
this.swap(leftIndex, index);
this.shiftDown(leftIndex);
}
}else{
if(this.heap[leftIndex] < this.heap[index]){
this.swap(leftIndex, index);
this.shiftDown(leftIndex);
}
}
}else{
//如果左右子节点都存在，则比较左右子节点的大小
if(this.type == "max"){
if(this.heap[leftIndex] > this.heap[index] && this.heap[leftIndex] >= this.heap[rightIndex]){
this.swap(leftIndex, index);
this.shiftDown(leftIndex);
}else if(this.heap[rightIndex] > this.heap[index] && this.heap[rightIndex] > this.heap[leftIndex]){
this.swap(rightIndex, index);
this.shiftDown(rightIndex);
}
}else{
if(this.heap[leftIndex] < this.heap[index] && this.heap[leftIndex] <= this.heap[rightIndex]){
this.swap(leftIndex, index);
this.shiftDown(leftIndex);
}else if(this.heap[rightIndex] < this.heap[index] && this.heap[rightIndex] < this.heap[leftIndex]){
this.swap(rightIndex, index);
this.shiftDown(rightIndex);
}
}
}
}
//获取左子
this.getLeftIndex = function(index){
return index * 2 + 1;
}
//获取右子节点
this.getRightIndex = function(index){
return index * 2 + 2;
}
return this;
}
</script>
</html>
