# 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.

https://www.geeksforgeeks.org/binary-heap/

## Heap Template

### Priority Queue in Java

https://stackoverflow.com/questions/6065710/how-does-javas-priorityqueue-differ-from-a-min-heap

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

https://github.com/awangdev/LintCode/blob/master/Java/HashHeap.java

``````// 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.

https://www.tutorialspoint.com/data_structures_algorithms/heap_data_structure.htm

## 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.
``````

## Reference

[Heap Data Structures](https://www.tutorialspoint.com/data_structures_algorithms/heap_data_structure.htm\

[GeeksforGeeks](https://www.geeksforgeeks.org/binary-heap/\

[HackerRank Heaps](https://www.hackerrank.com/topics/heaps

PriorityQueue: https://algs4.cs.princeton.edu/24pq/