Comment on page

# Heap

## Heap 操作

• 插入: 将新元素放到`heap[size+1]`的位置每次比较它的它父亲元素，如果小于它的父亲，证明现在不满 足堆的性质，然后向上Sift Up
• 删除: 将根节点和最后一个节点进行交换如果该节点大于其中一个儿子，那么将其与其较小的儿子进行交换做Sift Down，直到该节点的儿子均大于它的值，或者它的儿子为空

### Heap

Interface 接口 • O(logN) Push -> Sift Up • O(logN) Pop -> Sift Down • O(1) Top • O(N) Delete

## Heap Application

Priority Queue: Priority queues can be efficiently implemented using Binary Heap because it supports insert(), delete() and extractmax(), decreaseKey() operations in O(logn) time.

## Heap Template

### Priority Queue in Java

The default PriorityQueue is implemented with Min-Heap, that is the top element is the minimum one in the heap. In order to implement a max-heap, you can create your own Comparator:
import java.util.Comparator;
public class MyComparator implements Comparator<Integer>
{
public int compare( Integer x, Integer y )
{
return y - x;
}
}
PriorityQueue minHeap = new PriorityQueue(); // default natural ordering; min-heap
PriorityQueue maxHeap = new PriorityQueue(size, new MyComparator());

### HashHeap

// HashHeap Implementation
// 接口
// • O(logN) Push -> Sift Up
// • O(logN) Pop -> Sift Down • O(1) Top
// • O(logN) Delete
class HashHeap {
ArrayList<Integer> heap;
String mode;
int size_t;
HashMap<Integer, Node> hash;
class Node {
public Integer id;
public Integer num;
Node(Node now) {
id = now.id;
num = now.num;
}
Node(Integer first, Integer second) {
this.id = first;
this.num = second;
}
}
public HashHeap(String mod) {
// TODO Auto-generated constructor stub
heap = new ArrayList<Integer>();
mode = mod;
hash = new HashMap<Integer, Node>();
size_t = 0;
}
int peak() {
return heap.get(0);
}
int size() {
return size_t;
}
Boolean empty() {
return (heap.size() == 0);
}
int parent(int id) {
if (id == 0) {
return -1;
}
return (id - 1) / 2;
}
int lson(int id) {
return id * 2 + 1;
}
int rson(int id) {
return id * 2 + 2;
}
boolean comparesmall(int a, int b) {
if (a <= b) {
if (mode == "min")
return true;
else
return false;
} else {
if (mode == "min")
return false;
else
return true;
}
}
void swap(int idA, int idB) {
int valA = heap.get(idA);
int valB = heap.get(idB);
int numA = hash.get(valA).num;
int numB = hash.get(valB).num;
hash.put(valB, new Node(idA, numB));
hash.put(valA, new Node(idB, numA));
heap.set(idA, valB);
heap.set(idB, valA);
}
Integer poll() {
size_t--;
Integer now = heap.get(0);
Node hashnow = hash.get(now);
if (hashnow.num == 1) {
swap(0, heap.size() - 1);
hash.remove(now);
heap.remove(heap.size() - 1);
if (heap.size() > 0) {
siftdown(0);
}
} else {
hash.put(now, new Node(0, hashnow.num - 1));
}
return now;
}
size_t++;
if (hash.containsKey(now)) {
Node hashnow = hash.get(now);
hash.put(now, new Node(hashnow.id, hashnow.num + 1));
} else {
hash.put(now, new Node(heap.size() - 1, 1));
}
siftup(heap.size() - 1);
}
void delete(int now) {
size_t--;
;
Node hashnow = hash.get(now);
int id = hashnow.id;
int num = hashnow.num;
if (hashnow.num == 1) {
swap(id, heap.size() - 1);
hash.remove(now);
heap.remove(heap.size() - 1);
if (heap.size() > id) {
siftup(id);
siftdown(id);
}
} else {
hash.put(now, new Node(id, num - 1));
}
}
void siftup(int id) {
while (parent(id) > -1) {
int parentId = parent(id);
if (comparesmall(heap.get(parentId), heap.get(id)) == true) {
break;
} else {
swap(id, parentId);
}
id = parentId;
}
}
void siftdown(int id) {
while (lson(id) < heap.size()) {
int leftId = lson(id);
int rightId = rson(id);
int son;
if (rightId >= heap.size() || (comparesmall(heap.get(leftId), heap.get(rightId)) == true)) {
son = leftId;
} else {
son = rightId;
}
if (comparesmall(heap.get(id), heap.get(son)) == true) {
break;
} else {
swap(id, son);
}
id = son;
}
}
}

## Heap Definition

(Binary) Heap is a special case of balanced binary tree data structure where the root-node key is compared with its children and arranged accordingly.
Min-Heap − Where the value of the root node is less than or equal to either of its children.
Max-Heap − Where the value of the root node is greater than or equal to either of its children.

## Heap Construction

### Max Heap Construction Algorithm

Step 1 − Create a new node at the end of heap.
Step 2 − Assign new value to the node.
Step 3 − Compare the value of this child node with its parent.
Step 4 − If value of parent is less than child, then swap them.
Step 5 − Repeat step 3 & 4 until Heap property holds.
Note − In Min Heap construction algorithm, we expect the value of the parent node to be less than that of the child node.

### Max Heap Deletion Algorithm

Deletion in Max (or Min) Heap always happens at the root to remove the Maximum (or minimum) value.
Step 1 − Remove root node.
Step 2 − Move the last element of last level to root.
Step 3 − Compare the value of this child node with its parent.
Step 4 − If value of parent is less than child, then swap them.
Step 5 − Repeat step 3 & 4 until Heap property holds.