// Java
import java.util.Arrays;
import java.util.NoSuchElementException;
public class BinaryHeap {
private static final int d = 2;
private int[] heap;
private int heapSize;
/**
* This will initialize our heap with default size.
*/
public BinaryHeap(int capacity) {
heapSize = 0;
heap = new int[capacity + 1];
Arrays.fill(heap, -1);
}
public boolean isEmpty() {
return heapSize == 0;
}
public boolean isFull() {
return heapSize == heap.length;
}
private int parent(int i) {
return (i - 1) / d;
}
private int kthChild(int i, int k) {
return d * i + k;
}
/**
* Inserts new element in to heap
* Complexity: O(log N)
* As worst case scenario, we need to traverse till the root
*/
public void insert(int x) {
if (isFull()) {
throw new NoSuchElementException("Heap is full, No space to insert new element");
}
heap[heapSize] = x;
heapSize ++;
heapifyUp(heapSize - 1);
}
/**
* Deletes element at index x
* Complexity: O(log N)
*/
public int delete(int x) {
if (isEmpty()) {
throw new NoSuchElementException("Heap is empty, No element to delete");
}
int maxElement = heap[x];
heap[x] = heap[heapSize - 1];
heapSize--;
heapifyDown(x);
return maxElement;
}
/**
* Maintains the heap property while inserting an element.
*/
private void heapifyUp(int i) {
int insertValue = heap[i];
while (i > 0 && insertValue > heap[parent(i)]) {
heap[i] = heap[parent(i)];
i = parent(i);
}
heap[i] = insertValue;
}
/**
* Maintains the heap property while deleting an element.
*/
private void heapifyDown(int i) {
int child;
int temp = heap[i];
while (kthChild(i, 1) < heapSize) {
child = maxChild(i);
if (temp >= heap[child]) {
break;
}
heap[i] = heap[child];
i = child;
}
heap[i] = temp;
}
private int maxChild(int i) {
int leftChild = kthChild(i, 1);
int rightChild = kthChild(i, 2);
return heap[leftChild] > heap[rightChild] ? leftChild : rightChild;
}
/**
* Prints all elements of the heap
*/
public void printHeap() {
System.out.print("nHeap = ");
for (int i = 0; i < heapSize; i++)
System.out.print(heap[i] + " ");
System.out.println();
}
/**
* This method returns the max element of the heap.
* complexity: O(1)
*/
public int findMax() {
if (isEmpty())
throw new NoSuchElementException("Heap is empty.");
return heap[0];
}
public static void main(String[] args) {
BinaryHeap maxHeap = new BinaryHeap(10);
maxHeap.insert(10);
maxHeap.insert(4);
maxHeap.insert(9);
maxHeap.insert(1);
maxHeap.insert(7);
maxHeap.insert(5);
maxHeap.insert(3);
maxHeap.printHeap();
maxHeap.delete(5);
maxHeap.printHeap();
maxHeap.delete(2);
maxHeap.printHeap();
}
}
C/C++
#include <iostream>
using namespace std;
class BinaryHeap {
public:
BinaryHeap(int capacity);
void insert(int x);
int erase(int x);
int findMax();
void printHeap();
bool isEmpty() { return heapSize == 0; }
bool isFull() { return heapSize == capacity; }
~BinaryHeap() { delete[] heap; }
private:
void heapifyUp(int i);
void heapifyDown(int i);
int maxChild(int i);
int parent(int i) { return (i - 1) / 2; }
int kthChild(int i, int k) { return 2 * i + k; }
private:
int *heap;
int heapSize;
int capacity;
};
/**
* This will initialize our heap with default size.
*/
BinaryHeap::BinaryHeap(int capacity) {
this->heapSize = 0;
this->capacity = capacity;
this->heap = new int[capacity + 5];
}
/**
* Inserts new element in to heap
* Complexity: O(log N)
* As worst case scenario, we need to traverse till the root
*/
void BinaryHeap::insert(int x) {
try {
if (isFull())
throw -1;
heap[heapSize] = x;
heapSize ++;
heapifyUp(heapSize - 1);
return ;
} catch (int e) {
cout << "Heap is full, No space to insert new element" << endl;
exit(-1);
}
}
/**
* Deletes element at index x
* Complexity: O(log N)
*/
int BinaryHeap::erase(int x) {
try {
if (isEmpty())
throw -1;
int maxElement = heap[x];
heap[x] = heap[heapSize - 1];
heapSize--;
heapifyDown(x);
return maxElement;
} catch (int e) {
cout << "Heap is empty, No element to delete" << endl;
exit(-1);
}
}
/**
* Maintains the heap property while inserting an element.
*/
void BinaryHeap::heapifyUp(int i) {
int insertValue = heap[i];
while (i > 0 && insertValue > heap[parent(i)]) {
heap[i] = heap[parent(i)];
i = parent(i);
}
heap[i] = insertValue;
}
/**
* Maintains the heap property while deleting an element.
*/
void BinaryHeap::heapifyDown(int i) {
int child;
int temp = heap[i];
while (kthChild(i, 1) < heapSize) {
child = maxChild(i);
if (temp >= heap[child]) {
break;
}
heap[i] = heap[child];
i = child;
}
heap[i] = temp;
}
int BinaryHeap::maxChild(int i) {
int leftChild = kthChild(i, 1);
int rightChild = kthChild(i, 2);
return heap[leftChild] > heap[rightChild] ? leftChild : rightChild;
}
/**
* This method returns the max element of the heap.
* complexity: O(1)
*/
int BinaryHeap::findMax() {
try {
if (isEmpty())
throw -1;
return heap[0];
} catch (int e) {
cout << "Heap is empty." << endl;
exit(-1);
}
}
/**
* Prints all elements of the heap
*/
void BinaryHeap::printHeap() {
cout << "nHeap = ";
for (int i = 0; i < heapSize; i++)
cout << heap[i] << " ";
cout << endl;
return ;
}
int main() {
BinaryHeap maxHeap(10);
maxHeap.insert(10);
maxHeap.insert(4);
maxHeap.insert(9);
maxHeap.insert(1);
maxHeap.insert(7);
maxHeap.insert(5);
maxHeap.insert(3);
maxHeap.printHeap();
maxHeap.erase(5);
maxHeap.printHeap();
maxHeap.erase(2);
maxHeap.printHeap();
return 0;
}
// JavaScript
class BinaryHeap {
constructor(compare) {
this.data = [];
this.compare = compare;
}
insert(value) {
this.insertAt(this.data.length, value);
}
insertAt(index, value) {
this.data[index] = value;
// 对比当前节点与其父节点，如果当前节点更小就交换它们
while (index > 0 && this.compare(value, this.data[Math.floor((index - 1) / 2)]) < 0) {
this.data[index] = this.data[Math.floor((index - 1) / 2)];
this.data[Math.floor((index - 1) / 2)] = value;
index = Math.floor((index - 1) / 2);
}
}
delete(index) {
if (this.data.length === 0) return;
let value = this.data[index];
let i = index;
// fix heap
while (i < this.data.length) {
let left = i * 2 + 1;
let right = i * 2 + 2;
// 没有左子节点
if (left >= this.data.length) break;
// 没有右子节点
if (right >= this.data.length) {
this.data[i] = this.data[left];
i = left;
break;
}
// 比较左右子节点的大小，更小的补到父节点
if (this.compare(this.data[left], this.data[right]) < 0) {
this.data[i] = this.data[left];
i = left;
} else {
this.data[i] = this.data[right];
i = right;
}
}
// 查看最后的空位是不是最后的叶子节点
if (i < this.data.length - 1) {
this.insertAt(i, this.data.pop());
} else {
this.data.pop();
}
return value;
}
printHeap() {
console.log("nHeap = ");
console.log(this.data);
}
}
let maxHeap = new BinaryHeap((a, b) => b - a);
maxHeap.insert(10);
maxHeap.insert(4);
maxHeap.insert(9);
maxHeap.insert(1);
maxHeap.insert(7);
maxHeap.insert(5);
maxHeap.insert(3);
maxHeap.printHeap();
maxHeap.delete(5);
maxHeap.printHeap();
maxHeap.delete(2);
maxHeap.printHeap();
Python
import sys
class BinaryHeap:
def __init__(self, capacity):
self.capacity = capacity
self.size = 0
self.Heap = [0]*(self.capacity + 1)
self.Heap[0] = -1 * sys.maxsize
self.FRONT = 1
def parent(self, pos):
return pos//2
def leftChild(self, pos):
return 2 * pos
def rightChild(self, pos):
return (2 * pos) + 1
def isLeaf(self, pos):
if pos >= (self.size//2) and pos <= self.size:
return True
return False
def swap(self, fpos, spos):
self.Heap[fpos], self.Heap[spos] = self.Heap[spos], self.Heap[fpos]
def heapifyDown(self, pos):
if not self.isLeaf(pos):
if (self.Heap[pos] > self.Heap[self.leftChild(pos)] or
self.Heap[pos] > self.Heap[self.rightChild(pos)]):
if self.Heap[self.leftChild(pos)] < self.Heap[self.rightChild(pos)]:
self.swap(pos, self.leftChild(pos))
self.heapifyDown(self.leftChild(pos))
else:
self.swap(pos, self.rightChild(pos))
self.heapifyDown(self.rightChild(pos))
def insert(self, element):
if self.size >= self.capacity :
return
self.size+= 1
self.Heap[self.size] = element
current = self.size
while self.Heap[current] < self.Heap[self.parent(current)]:
self.swap(current, self.parent(current))
current = self.parent(current)
def Print(self):
for i in range(1, (self.size//2)+1):
print(" PARENT : "+ str(self.Heap[i])+" LEFT CHILD : "+
str(self.Heap[2 * i])+" RIGHT CHILD : "+
str(self.Heap[2 * i + 1]))
def minHeap(self):
for pos in range(self.size//2, 0, -1):
self.heapifyDown(pos)
def delete(self):
popped = self.Heap[self.FRONT]
self.Heap[self.FRONT] = self.Heap[self.size]
self.size-= 1
self.heapifyDown(self.FRONT)
return popped
def isEmpty(self):
return self.size == 0
def isFull(self):
return self.size == self.capacity
if __name__ == "__main__":
print('The minHeap is ')
minHeap = BinaryHeap(5)
minHeap.insert(5)
minHeap.insert(3)
minHeap.insert(17)
minHeap.insert(10)
minHeap.insert(84)
minHeap.insert(19)
minHeap.insert(6)
minHeap.insert(22)
minHeap.insert(9)
minHeap.minHeap()
minHeap.Print()
print("The Min val is " + str(minHeap.delete()))