二叉堆
实现二叉堆
JavaScript版
var parent = function (index) {
return Math.trunc((index - 1) / 2);
};
var leftChild = function (index) {
return index * 2 + 1;
};
var rightChild = function (index) {
return index * 2 + 2;
};
var shiftUp = function (arr, index) {
while (index > 0 && arr[index] > arr[parent(index)]) {
swap(arr, index, parent(index));
index = parent(index);
}
};
var shiftDown = function (arr, count, index) {
while (leftChild(index) < count) {
let maxIndex = leftChild(index);
if (rightChild(index) < count && arr[rightChild(index)] > arr[leftChild(index)]) {
maxIndex = rightChild(index);
}
if (arr[index] >= arr[maxIndex]) {
break;
}
swap(arr, index, maxIndex);
index = maxIndex;
}
};
var swap = function (arr, a, b) {
let temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
};
class Heap {
constructor(size) {
this._data = new Array(size);
this.size = size;
this.count = 0;
}
enqueue (element) {
if (this.count > this.size) {
throw new Error("enqueue failed, Heap is full")
}
this._data[this.count] = element;
this.count++;
shiftUp(this._data, this.count - 1);
}
dequeue () {
if (this.count <= 0) {
throw new Error("dequeue failed, Heap is empty")
}
const result = this._data[0];
swap(this._data, 0, this.count - 1);
this.count--;
shiftDown(this._data, this.count, 0);
return result;
}
}
var sortArray = function (nums) {
let heap = new Heap(nums.length)
for (let i = 0; i < nums.length; i++) {
heap.enqueue(nums[i]);
}
for(let i = nums.length - 1; i >= 0; i--) {
nums[i] = heap.dequeue();
}
return nums;
};
Java版
class Heap {
private int parent (int index) {
return (index - 1) / 2;
}
private int leftChild (int index) {
return 2 * index + 1;
}
private int rightChild (int index) {
return 2 * index + 2;
}
private void shiftUp (int[] arr, int index) {
while (index > 0 && arr[index] > arr[parent(index)]) {
swap(arr, index, parent(index));
index = parent(index);
}
}
private void shiftDown(int[] arr, int count, int index) {
while (leftChild(index) < count) {
int maxIndex = leftChild(index);
if (rightChild(index) < count && arr[rightChild(index)] > arr[leftChild(index)]) {
maxIndex = rightChild(index);
}
if (arr[index] >= arr[maxIndex]) {
break;
}
swap(arr, index, maxIndex);
index = maxIndex;
}
}
private void swap(int[] arr, int a, int b) {
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
private int[] data;
private int count;
private int size;
public Heap (int size) {
this.data = new int[size];
this.count = 0;
this.size = size;
}
public void enqueue (int element) {
if (this.count > this.size) {
throw new IllegalArgumentException("enqueue failed, Heap is full");
}
this.data[this.count] = element;
this.count++;
shiftUp(this.data, this.count - 1);
}
public int dequeue () {
if (this.count <= 0) {
throw new IllegalArgumentException("dequeue failed, Heap is empty");
}
int result = this.data[0];
swap(this.data, 0, this.count - 1);
this.count--;
shiftDown(this.data, this.count, 0);
return result;
}
}
class Solution {
public int[] sortArray(int[] nums) {
Heap heap = new Heap(nums.length);
for (int i = 0; i < nums.length; i++) {
heap.enqueue(nums[i]);
}
for (int i = nums.length - 1; i >= 0; i--) {
nums[i] = heap.dequeue();
}
return nums;
}
}
数组转堆
JavaScript版
var parent = function (index) {
return Math.trunc((index - 1) / 2);
};
var leftChild = function (index) {
return index * 2 + 1;
};
var rightChild = function (index) {
return index * 2 + 2;
};
var shiftDown = function (arr, count, index) {
while (leftChild(index) < count) {
let maxIndex = leftChild(index);
if (rightChild(index) < count && arr[rightChild(index)] > arr[leftChild(index)]) {
maxIndex = rightChild(index);
}
if (arr[index] >= arr[maxIndex]) {
break;
}
swap(arr, index, maxIndex);
index = maxIndex;
}
};
var swap = function (arr, a, b) {
let temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
};
class Heap {
constructor(arr) {
this._data = new Array(arr.length);
for (let i = 0; i < arr.length; i++) {
this._data[i] = arr[i];
}
this.count = arr.length;
for (let i = Math.trunc((this.count - 1) / 2); i >= 0; i--) {
shiftDown(this._data, this.count, i);
}
}
dequeue () {
const result = this._data[0];
swap(this._data, 0, this.count - 1);
this.count--;
shiftDown(this._data, this.count, 0);
return result;
}
}
var sortArray = function (nums) {
let heap = new Heap(nums)
for(let i = nums.length - 1; i >= 0; i--) {
nums[i] = heap.dequeue();
}
return nums;
};
Java版
class Heap {
private int parent (int index) {
return (index - 1) / 2;
}
private int leftChild (int index) {
return 2 * index + 1;
}
private int rightChild (int index) {
return 2 * index + 2;
}
private void shiftDown(int[] arr, int count, int index) {
while (leftChild(index) < count) {
int maxIndex = leftChild(index);
if (rightChild(index) < count && arr[rightChild(index)] > arr[leftChild(index)]) {
maxIndex = rightChild(index);
}
if (arr[index] >= arr[maxIndex]) {
break;
}
swap(arr, index, maxIndex);
index = maxIndex;
}
}
private void swap(int[] arr, int a, int b) {
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
private int[] data;
private int count;
private int size;
public Heap (int[] arr) {
this.data = new int[arr.length];
for (int i = 0; i < arr.length; i++) {
this.data[i] = arr[i];
}
this.count = arr.length;
for (int i = (this.count - 1) / 2; i >= 0; i--) {
shiftDown(this.data, this.count, i);
}
}
public int dequeue () {
if (this.count <= 0) {
throw new IllegalArgumentException("dequeue failed, Heap is empty");
}
int result = this.data[0];
swap(this.data, 0, this.count - 1);
this.count--;
shiftDown(this.data, this.count, 0);
return result;
}
}
class Solution {
public int[] sortArray(int[] nums) {
Heap heap = new Heap(nums);
for (int i = nums.length - 1; i >= 0; i--) {
nums[i] = heap.dequeue();
}
return nums;
}
}
Comments NOTHING