普通堆
<!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>
<script>
class MaxHeap{
constructor(arr){
this._data = []
if(arguments.length==1){
for(let i=0;i<arr.length;i++){
this._data[i+1]=arr[i];
}
this._count= arr.length;
for(let i=Math.floor(this._count/2);i>=1;i--){
this.shiftDown(i)
}
}else{
this._count = 0
}
}
swap(arr, a, b) {
var tmp = arr[b];
arr[b] = arr[a];
arr[a] = tmp;
}
size(){
return this._count;
}
isEmpty(){
return this._count==0;
}
insert(item){
this._data[this._count+1]=item;
this._count ++;
this.shiftUp(this._count);
}
shiftUp(k){
while(k>1 && this._data[Math.floor(k / 2)] < this._data[k]){
this.swap(this._data,Math.floor(k/2),k);
k=Math.floor(k / 2);
}
}
extractMax(){
let ret=this._data[1];
this.swap(this._data,1,this._count)
this._count --;
this.shiftDown(1)
return ret;
}
shiftDown(k){
while(2*k<= this._count){
let j=2*k;
if(j+1<= this._count&& this._data[j+1]> this._data[j])
j+=1;
if(this._data[k]>= this._data[j])
break;
this.swap(this._data,k,j)
k=j
}
}
}
function swap(arr,a,b){
var tmp=arr[b];
arr[b]=arr[a];
arr[a]=tmp;
}
function generateRandomArray(n, rangeL, rangeR) {
var arr = [];
for (var i = 0; i < n; i++) {
arr.push(Math.floor(Math.random() * (rangeR - rangeL + 1)) + rangeL)
}
return arr;
}
function heapSort1(arr){
let maxheap=new MaxHeap()
for(let i=0;i<arr.length;i++)
maxheap.insert(arr[i])
while(!maxheap.isEmpty())
arr[i]=maxheap.extractMax();
}
function heapSort2(arr){
let maxheap=new MaxHeap(arr)
while(!maxheap.isEmpty())
arr[i]=maxheap.extractMax();
}
function heapSort(arr){
function __shiftDown(arr,n,k){
while(2*k+1<n){
let j=2*k+1;
if(j+1<n&& arr[j+1]> arr[j])
j+=1;
if(arr[k]>= arr[j])
break;
swap(arr,k,j)
k=j
}
}
for(let i=Math.floor(arr.length-1/2);i>=0;i--)
__shiftDown(arr,arr.length,i)
for(let i=arr.length-1;i>0;i--){
swap(arr,0,i)
__shiftDown(arr,i,0)
}
}
heapSort(generateRandomArray(50,0,100))
</script>
</body>
</html>
索引堆
class IndexMaxHeap{
constructor(arr){
this._data = []
this._indexes=[]
if(arguments.length==1){
for(let i=0;i<arr.length;i++){
this._data[i+1]=arr[i];
}
this._count= arr.length;
for(let i=Math.floor(this._count/2);i>=1;i--){
this.shiftDown(i)
}
}else{
this._count = 0
}
}
swap(arr, a, b) {
var tmp = arr[b];
arr[b] = arr[a];
arr[a] = tmp;
}
size(){
return this._count;
}
isEmpty(){
return this._count==0;
}
//传入的i对用户而言，是从0开始索引的
insert(i,item){
i+=1;
this._data[i]=item;
this._indexes[this._count+1]=i
this._count ++;
this.shiftUp(this._count);
}
shiftUp(k){
while(k>1 && this._data[this._indexes[Math.floor(k / 2)]] < this._data[this._indexes[k]]){
this.swap(this._indexes,Math.floor(k/2),k);
k=Math.floor(k / 2);
}
}
extractMax(){
let ret=this._data[this._indexes[1]];
this.swap(this._indexes,1,this._count)
this._count --;
this.shiftDown(1)
return ret;
}
extractMaxIndex(){
let ret=this._indexes[1]-1;
this.swap(this._indexes,1,this._count)
this._count --;
this.shiftDown(1)
return ret;
}
getItem(i){
return this._data[i+1]
}
change(i,newItem){
i+=1;
this._data[i]=newItem;
for(let j=1;j<=count;j++){
if(this._indexes[j]==i){
shiftUp(j);
shiftDown(j);
}
}
}
shiftDown(k){
while(2*k<= this._count){
let j=2*k;
if(j+1<= this._count&& this._data[this._indexes[j+1]]> this._data[this._indexes[j]])
j+=1;
if(this._data[this._indexes[k]]>= this._data[this._indexes[j]])
break;
this.swap(this._indexes,k,j)
k=j
}
}
}
用reverse优化过的索引堆
class IndexMaxHeap {
constructor(arr) {
this._data = []
this._indexes = []
this._reverse = []
for(let i=0;i<=arr.length;i++)
this._reverse[i]=0;
if (arguments.length == 1) {
for (let i = 0; i < arr.length; i++) {
this._data[i + 1] = arr[i];
}
this._count = arr.length;
for (let i = Math.floor(this._count / 2); i >= 1; i--) {
this.shiftDown(i)
}
} else {
this._count = 0
}
}
swap(arr, a, b) {
var tmp = arr[b];
arr[b] = arr[a];
arr[a] = tmp;
}
size() {
return this._count;
}
isEmpty() {
return this._count == 0;
}
//传入的i对用户而言，是从0开始索引的
insert(i, item) {
i += 1;
this._data[i] = item;
this._indexes[this._count + 1] = i
this._reverse[i] = this._count + 1
this._count++;
this.shiftUp(this._count);
}
shiftUp(k) {
while (k > 1 && this._data[this._indexes[Math.floor(k / 2)]] < this._data[this._indexes[k]]) {
this.swap(this._indexes, Math.floor(k / 2), k);
this._reverse[this._indexes[Math.floor(k / 2)]]= Math.floor(k / 2)
this._reverse[this._indexes[k]] = k
k = Math.floor(k / 2);
}
}
extractMax() {
let ret = this._data[this._indexes[1]];
this.swap(this._indexes, 1, this._count)
this._reverse[this._indexes[1]]=1
this._reverse[this._indexes[this._count]] = 0
this._count--;
this.shiftDown(1)
return ret;
}
extractMaxIndex() {
let ret = this._indexes[1] - 1;
this.swap(this._indexes, 1, this._count)
this._reverse[this._indexes[1]] = 1
this._reverse[this._indexes[this._count]] = 0
this._count--;
this.shiftDown(1)
return ret;
}
getItem(i) {
return this._data[i + 1]
}
change(i, newItem) {
i += 1;
this._data[i] = newItem;
/* for (let j = 1; j <= count; j++) {
if (this._indexes[j] == i) {
shiftUp(j);
shiftDown(j);
}
} */
let j=this._reverse[i]
this.shiftUp(j)
this.shiftDown(j)
}
shiftDown(k) {
while (2 * k <= this._count) {
let j = 2 * k;
if (j + 1 <= this._count && this._data[this._indexes[j + 1]] > this._data[this._indexes[j]])
j += 1;
if (this._data[this._indexes[k]] >= this._data[this._indexes[j]])
break;
this.swap(this._indexes, k, j)
this._reverse[this._index[k]] = k
this._reverse[this._index[j]] = j
k = j
}
}
}
网友评论