CS/자료구조(Data Structure)
[자료구조] Heap 힙, 우선순위 큐
ysk(0soo)
2022. 8. 14. 18:56
힙(Heap)
힙(heap)은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리를 기본으로 한 자료구조이다.
힙에는 두가지 종류가 있다.
- 부모노드의 키값이 자식노드의 키값보다 항상 큰 힙 : 최대 힙(Max Heap)
- 부모노드의 키값이 자식노드의 키값보다 항상 작은 힙 : 최소 힙(Min Heap)
우선 순위 큐(Priority queue)를 위해서 만들어졌다. - 힙 자체가 우선순위 큐이다.
큐는 FIFO(First In First Out, 선입선출) 자료구조인데,
우선순위큐는 들어간 순서에 상관 없이 우선순위가 높은 데이터가 먼저 나온다.
Queue의 시간 복잡도는 enqueue = O(1), dequeue O(1) 이고
Priority queue 의 시간 복잡도는 push(삽입, O(log N)), pop (삭제 O(log N)) 이다.
다만 검색은(특정 값을 찾는것) 위치에 대한 개념이 없기 떄문에 선형시간 O(n) 이다
- 자바 PriorityQueue 도 선형으로 되어있다.
시뮬레이션 시스템, 작업 스케줄링, 수치해석 계산에 사용된다.
Tree의 형식을 취하고 있으며 Tree 중에서도 배열을 기반으로 한 (Complete Binary Tree)완전 이진 트리이다.
최대값 및 최소값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전 이진 트리이다.
배열에 트리의 값을 넣어줄 때는 0번째는 건너뛰고 1번째부터 루트 노드가 시작된다. 이유는 노드의 고유 번호와 index를 일치시켜 혼동을 줄이기 위함이다.
중복된 값을 허용. (이진 탐색 트리는 중복 값을 허용하지 않음.)
Max Heap은 루트 노드에 저장된 값이 가장 크다.
Min Heap은 루트 노드에 저장된 값이 가장 작은값이 된다.
최대힙에서는 Root Node에 있는 값이 제일 크므로, 최대값을 찾는데 소요되는 연산의 시간 복잡도는 O(1)이다.
Complete Binary Tree이기 때문에 배열을 이용해 관리할 수 있으며, 인덱스를 통한 Random Access가 가능하다.
Index 번호는 노드 개수가 n개일 때, i번째 노드에 대하여 왼쪽 자식은 ix2, 오른쪽 자식은 ix2+1가 된다.
구현
힙을 저장하는 표준적인 자료구조는 배열이다.
구현을 쉽게 하기 위해 배열의 첫 번째 인덱스인 0은 사용되지 않고, 1부터 시작한다.첫 번째 인덱스인 0 번을 사용하는 경우도 있는데, 그러면 부모 노드와 자식 노드의 관계 공식이 달라진다.
특정 위치의 노드 번호는 새로운 노드가 추가되어도 변하지 않는다.
<부모 노드와 자식 노드의 관계>
- 왼쪽 자식 index : (부모 index) * 2
- n번째 노드의 왼쪽 자식 = 2n
- 오른쪽 자식 index : (부모 index) * 2 + 1
- n번째 노드의 오른쪽 자식 = 2n + 1
- 부모 index : (자식 index) / 2
- n번째 노드의 부모 = n / 2
- 힙의 높이는l og(N) 이다.
- push 했을 때 스왑하는 과정이 최대 logN번 반복되기 떄문에 시간복잡도는 O(log N)
삽입
MaxHeap
- 힙에 새로운 요소가 들어오면 새로운 요소를 마지막노드에 삽입.
- bottom-up 방식으로 새 요소와 크기를 비교해가면서
새로운 요소보다 부모가 더 작으면 swap
int index = lastIndex(); // 마지막 인덱스. 이 기준은 루트 인덱스가 1로 가정했을때이다. while (부모가 존재하는가? && 그렇다면 부모가 나보다 값이 작은가?){ swap(부모인덱스, 내 인덱스); index = 부모인덱스 // 스왑했으니까 부모가 되고, 다음 조건에 맞으면 새 부모와 다시 비교한다. }heapifyUp()
- bottom-up 방식으로 새 요소와 크기를 비교해가면서
MinHeap
- 힙에 새로운 요소가 들어오면, 일단 새로운 노드를 힙의 마지막 노드에 삽입.
- bottom-up 방식으로 새로운 요소와 크기를 비교해가면서
부모가 더 크면 부모와 swap
int childIndex = lastIndex(); while (부모가 존재하는가? && 그렇다면 부모가 나보다 값이 큰가?) { swap(부모인덱스, 내 인덱스); childIndex = 부모인덱스 // 스왑했으니까 부모가 되고, 다음 조건에 맞으면 새 부모와 다시 비교한다. }heapfiyUp();
- bottom-up 방식으로 새로운 요소와 크기를 비교해가면서
- max heap일 때 들어온 값, 부모 중 부모가 작으면 부모랑 교환한다 - 부모값이 더 커야 하므로
- min heap일 때 들어올 값, 부모 중 부모가 크면 부모랑 교환한다 - 부모값이 더 작아야 하므로
힙 재구성을 heapify라고 하겠습니다.
힙을 재구성 할때는 insert와 delete시 방법이 다르다.
insert - heapifyUp
- 마지막 인덱스부터 루트 인덱스까지 bottom-up 방식으로 크기를 비교해서 재구성한다
delete - heapfiyDown
- 루트 인덱스부터 마지막 인덱스까지 top-down 방식으로 크기를 비교해서 재구성 한다.
삭제
MaxHeap
- 힙의 루트 에서 값을 빼고, 마지막 인덱스의 값을 힙의 루트로 삽입.
top-down 방식으로 새 루트 요소와 왼쪽 오른쪽 자식들을 비교하면서,
더 큰 값의 자식과 swapint parentIndex = 1; // 인덱스를 0에서 시작하느냐, 1에서 시작하느냐에 따름. 루트 인덱스 값 while (왼쪽 자식이 있느냐(부모인덱스)){ // 왼쪽 자식이 없으면 오른쪽 자식은 없다. int bigChildIndex = getLeftChildIndex(parentIndex); // if (오른쪽 자식이 있고 && 오른쪽 자식이 왼쪽 자식보다 크다면) { bigChildIndex = 오른쪽 자식인덱스; } if (부모값이 자식값보다 크다면) { break; } else { // 부모 값이 자식보다 작다면 swap(부모인덱스, 더 큰 자식 인덱스); parentIndex = 더 큰 자식 인덱스; // 반복해가면서 비교한다 } }heapfiyDown();
MinHeap
- 힙의 루트에서 값을 빼고 마지막 인덱스의 값을 힙의 루트로 삽입
- top-down 방식으로 새 루트 요소와 왼쪽, 오른쪽 자식들이 값을 비교하면서
더 작은 값의 자식과 swap
int parentIndex = 1; //인덱스를 0에서 시작하느냐, 1에서 시작하느냐에 따름. 루트 인덱스 값 while (왼쪽 자식이 있느냐(부모인덱스)) { int smallChildIndex = getLeftChildIndex(parentIndex); if (오른쪽 자식이 있꼬 && 오른쪽 자식이 왼쪽 자식보다 더 작다면) { smallChildIndex = 오른쪽 자식인덱스; } if (부모 값이 자식보다 작다면) { break; } else { // 부모 값이 자식보다 크다면 swap(부모 인덱스, 더 작은 자식 인덱스); parentIndex = 더 작은 자식인덱스; } }heapifyDown();
- top-down 방식으로 새 루트 요소와 왼쪽, 오른쪽 자식들이 값을 비교하면서
Java Code(자바 코드) - 배열과 ArrayList를 사용한 2가지 방식.
ArrayList 사용 - 접기/펼치기
추상클래스 이용하여 구현public abstract class ListHeap<T> {
abstract void add(T data);
abstract T pop();
abstract void heapifyUp();
abstract void heapifyDown();
abstract T peek();
abstract int size();
abstract boolean contains(T data);
abstract void swap(int i, int j);
protected int getParentIndex(int childIndex) {
return (int) Math.floor((int) ((childIndex - 1) / 2));// 바닥함수. 내려야한다.
}
protected int getLeftChildIndex(int parentIndex) {
return (2 * parentIndex) + 1;
}
protected int getRightChildIndex(int parentIndex) {
return (2 * parentIndex) + 2;
}
protected boolean hasRightChild(int index) {
return getRightChildIndex(index) < size();
}
protected boolean hasLeftChild(int index) {
return getLeftChildIndex(index) < size();
}
protected boolean hasParent(int index) {
return getParentIndex(index) >= 0;
}
protected int lastIndex() {
return this.size() - 1;
}
public void printElements() {
while (this.size() > 0) {
System.out.print(this.pop() + (this.size() != 1 ? ", " : ""));
}
}
}
public class ArrayListMaxHeap<T extends Comparable<T>> extends ListHeap<T> {
private final List<T> elements;
public ArrayListMaxHeap() {
this.elements = new ArrayList<>();
}
@Override
public void swap(int i, int j) {
final T temp = elements.get(i);
elements.set(i, elements.get(j));
elements.set(j, temp);
}
private boolean isRightChildBigThenLeftChild(int parentIndex) {
return elements.get(getRightChildIndex(parentIndex)).compareTo(elements.get(getLeftChildIndex(parentIndex))) > 0;
}
private boolean isParentBiggerThenBigChild(int parentIndex, int childIndex) {
return elements.get(parentIndex).compareTo(elements.get(childIndex)) > 0;
}
private boolean isParentSmallThenChild(int childIndex) {
return elements.get(getParentIndex(childIndex)).compareTo(elements.get(childIndex)) < 0;
}
@Override
public void add(T data) {
elements.add(data);
heapifyUp();
}
@Override
protected void heapifyUp() {
int childIndex = lastIndex();
while (hasParent(childIndex) && isParentSmallThenChild(childIndex)) {
swap(getParentIndex(childIndex), childIndex);
childIndex = getParentIndex(childIndex);
}
}
@Override
public T pop() {
if (this.size() == 0) {
throw new ArrayIndexOutOfBoundsException("heap is empty");
}
final T pop = elements.get(0);
elements.set(0, elements.get(lastIndex()));
elements.remove(lastIndex());
heapifyDown();
return pop;
}
@Override
protected void heapifyDown() {
int index = 0;
while (hasLeftChild(index)) { // 왼쪽 자식이 없으면 오른쪽 자식도 없다.
int bigChildIndex = getLeftChildIndex(index);
if (hasRightChild(index) && isRightChildBigThenLeftChild(index)) {
bigChildIndex = getRightChildIndex(index);
}
if (isParentBiggerThenBigChild(index, bigChildIndex)) {
break;
} else {
swap(bigChildIndex, index);
index = bigChildIndex;
}
}
}
@Override
public T peek() {
return this.elements.get(0);
}
@Override
int size() {
return this.elements.size();
}
@Override
boolean contains(T data) {
return this.elements.contains(data);
}
public static void main(String[] args) {
ListHeap<Integer> arrayListListHeap = new ArrayListMaxHeap<>();
arrayListListHeap.add(5);
arrayListListHeap.add(4);
arrayListListHeap.add(2);
arrayListListHeap.add(7);
arrayListListHeap.add(8);
arrayListListHeap.add(9);
arrayListListHeap.add(3);
arrayListListHeap.add(6);
arrayListListHeap.add(15);
arrayListListHeap.add(999);
arrayListListHeap.add(21);
arrayListListHeap.add(1);
arrayListListHeap.add(2393);
arrayListListHeap.add(8237);
arrayListListHeap.add(9999);
arrayListListHeap.add(999);
arrayListListHeap.add(999);
arrayListListHeap.add(999);
arrayListListHeap.printElements();
}
}
public class ArrayListMinHeap<T extends Comparable<T>> extends ListHeap<T> {
private final List<T> elements;
public ArrayListMinHeap() {
this.elements = new ArrayList<>();
}
@Override
public void add(T data) {
elements.add(data);
heapifyUp();
}
@Override
public T pop() {
if (this.size() == 0) {
throw new ArrayIndexOutOfBoundsException("heap is empty");
}
final T pop = elements.get(0);
elements.set(0, elements.get(lastIndex()));
elements.remove(lastIndex());
heapifyDown();
return pop;
}
private boolean isParentBigThenChild(int childIndex) {
return elements.get(getParentIndex(childIndex)).compareTo(elements.get(childIndex)) > 0;
}
@Override
protected void heapifyUp() {
int childIndex = lastIndex();
while (hasParent(childIndex) && isParentBigThenChild(childIndex)) {
swap(getParentIndex(childIndex), childIndex);
childIndex = getParentIndex(childIndex);
}
}
@Override
protected void heapifyDown() {
int index = 0;
while (hasLeftChild(index)) { // 왼쪽 자식이 없으면 오른쪽 자식도 없다.
int smallChildIndex = getLeftChildIndex(index);
if (hasRightChild(index) && isRightChildSmallThenLeftChild(index)) {
smallChildIndex = getRightChildIndex(index);
}
if (isParentSmallThenSmallChild(index, smallChildIndex)) {
break;
} else {
swap(smallChildIndex, index);
index = smallChildIndex;
}
}
}
private boolean isParentSmallThenSmallChild(int parentIndex, int childIndex) {
return elements.get(parentIndex).compareTo(elements.get(childIndex)) < 0;
}
private boolean isRightChildSmallThenLeftChild(int parentIndex) {
return elements.get(getRightChildIndex(parentIndex)).compareTo(elements.get(getLeftChildIndex(parentIndex))) < 0;
}
@Override
public T peek() {
return this.elements.get(0);
}
@Override
public int size() {
return this.elements.size();
}
@Override
public boolean contains(T data) {
return this.elements.contains(data);
}
@Override
protected void swap(int i, int j) {
final T temp = elements.get(i);
elements.set(i, elements.get(j));
elements.set(j, temp);
}
public static void main(String[] args) {
ListHeap<Integer> arrayListListHeap = new ArrayListMinHeap<>();
arrayListListHeap.add(5);
arrayListListHeap.add(4);
arrayListListHeap.add(2);
arrayListListHeap.add(7);
arrayListListHeap.add(8);
arrayListListHeap.add(9);
arrayListListHeap.add(3);
arrayListListHeap.add(6);
arrayListListHeap.add(15);
arrayListListHeap.add(999);
arrayListListHeap.add(21);
arrayListListHeap.add(1);
arrayListListHeap.add(2393);
arrayListListHeap.add(8237);
arrayListListHeap.add(9999);
arrayListListHeap.add(999);
arrayListListHeap.add(999);
arrayListListHeap.add(999);
arrayListListHeap.printElements();
}
}
배열을 이용한 힙 구현 - 접기/펼치기
public interface ArrayHeap {
void add(int data);
void printElements();
boolean contains(int data);
int peek();
int pop();
int size();
default int getParentIndex(int childIndex) {
return (int) Math.floor(childIndex / 2);// 바닥함수. 내려야한다.
}
default int getLeftChildIndex(int parentIndex) {
return (2 * parentIndex) + 1;
}
default int getRightChildIndex(int parentIndex) {
return (2 * parentIndex) + 2;
}
default boolean hasParent(int index) {
return getParentIndex(index) >= 0;
}
}
public class ArrayMaxHeap implements ArrayHeap {
private int[] element;
private int size;
private int maxSize;
public ArrayMaxHeap(int maxSize) {
this.maxSize = maxSize;
this.element = new int[maxSize + 1];
this.size = 0;
}
private int leftChildValue(int parentIndex) {
return element[getLeftChildIndex(parentIndex)];
}
private int rightChildValue(int parentIndex) {
return element[getRightChildIndex(parentIndex)];
}
private int parentValueFromChild(int childIndex) {
return element[getParentIndex(childIndex)];
}
private int parentValue(int parentIndex) {
return element[parentIndex];
}
private int getParentData(int index) {
return element[getParentIndex(index)];
}
private boolean isGraterThenChild(int parentIndex) {
return parentValue(parentIndex) > leftChildValue(parentIndex) && parentValue(parentIndex) > rightChildValue(parentIndex);
}
private void swap(int targetIndex, int otherIndex) {
int temp = element[targetIndex];
element[targetIndex] = element[otherIndex];
element[otherIndex] = temp;
}
@Override
public void add(int data) {
validateSizeAndResize();
this.element[++size] = data;
heapifyUpUseWhile(); // or heapifyUpUseFor();
}
// insert 할때는 마지막 인덱스부터 루트 인덱스(1) 까지 bottom-up 방식으로 크기를 비교해서 재구성 한다.
// maxHeap은 큰값이 부모가 되어야 한다
private void heapifyUpUseFor() {
for (int i = size; i > 1; i--) {
int parentIndex = getParentIndex(i);
if (element[parentIndex] < element[i]) {
swap(parentIndex, i);
}
}
}
// insert 할때는 마지막 인덱스부터 루트 인덱스(1) 까지 bottom-up 방식으로 크기를 비교해서 재구성 한다.
private void heapifyUpUseWhile() {
int childIndex = size;
while (hasParent(childIndex) && getParentData(childIndex) < element[childIndex]) {
swap(getParentIndex(childIndex), childIndex);
childIndex = getParentIndex(childIndex);
}
}
private void validateSizeAndResize() {
if (size == this.maxSize) {
element = Arrays.copyOf(element, maxSize * 2);
maxSize *= 2;
}
}
@Override
public int pop() {
if (size == 0) {
throw new ArrayIndexOutOfBoundsException("heap is empty");
}
int root = element[1];
element[1] = element[size];
element[size] = 0;
this.size = size - 1;
heapifyDownUseFor();// or heapifyDownUserWhile();
return root;
}
// delete 할때는 루트 인덱스부터 마지막 인덱스까지 top-down 크기를 비교해서 재구성 한다.
public void heapifyDownUseFor() {
for (int parent = 1; parent * 2 <= size; ) {
if (isGraterThenChild(parent)) {
break;
} else if (leftChildValue(parent) > rightChildValue(parent)) {
swap(parent, getLeftChildIndex(parent));
parent = parent * 2;
} else {
swap(parent, getRightChildIndex(parent));
parent = parent * 2 + 1;
}
}
}
public void heapifyDownUserWhile() {
int parent = 1;
while (parent * 2 <= size) {
if (isGraterThenChild(parent)) {
break;
} else if (leftChildValue(parent) > rightChildValue(parent)) {
swap(parent, getLeftChildIndex(parent));
parent = parent * 2;
} else {
swap(parent, getRightChildIndex(parent));
parent = parent * 2 + 1;
}
}
}
@Override
public void printElements() {
if (this.size == 0) {
return;
}
while (!(this.size == 0)) {
System.out.print(pop() + ", ");
}
}
@Override
public boolean contains(int data) {
for (int i = 1; i <= size; i++) {
if (element[i] == data) {
return true;
}
}
return false;
}
@Override
public int peek() {
return element[1];
}
@Override
public int size() {
return this.size;
}
public static void main(String[] args) {
ArrayHeap arrayMaxHeap = new ArrayMaxHeap(10);
arrayMaxHeap.add(5);
arrayMaxHeap.add(4);
arrayMaxHeap.add(2);
arrayMaxHeap.add(7);
arrayMaxHeap.add(8);
arrayMaxHeap.add(9);
arrayMaxHeap.add(3);
arrayMaxHeap.add(6);
arrayMaxHeap.add(15);
arrayMaxHeap.add(999);
arrayMaxHeap.add(2134134);
arrayMaxHeap.add(21);
arrayMaxHeap.add(1);
arrayMaxHeap.add(9918324);
arrayMaxHeap.add(239328);
arrayMaxHeap.add(8237237);
arrayMaxHeap.add(99999999);
arrayMaxHeap.printElements();
}
}
public class ArrayMinHeap implements ArrayHeap {
private int[] element;
private int size;
private int maxSize;
private int leftChildValue(int parentIndex) {
return element[getLeftChildIndex(parentIndex)];
}
private int rightChildValue(int parentIndex) {
return element[getRightChildIndex(parentIndex)];
}
private int parentValue(int parentIndex) {
return element[parentIndex];
}
private int getParentData(int index) {
return element[getParentIndex(index)];
}
private boolean hasLeftChild(int index) { // 배열이기때문에 음수 값도 들어갈수 있어서 값 대신 size로 비교
return getLeftChildIndex(index) < size;
}
private boolean hasRightChild(int index) { // 배열이기때문에 음수 값도 들어갈수 있어서 값 대신 size로 비교
return getRightChildIndex(index) < size;
}
@Override
public boolean hasParent(int index) {
return getParentIndex(index) >= 1;
}
private void swap(int targetIndex, int otherIndex) {
int temp = element[targetIndex];
element[targetIndex] = element[otherIndex];
element[otherIndex] = temp;
}
private void validateSizeAndResize() {
if (size == this.maxSize) {
element = Arrays.copyOf(element, maxSize * 2);
maxSize *= 2;
}
}
public ArrayMinHeap(int maxSize) {
this.maxSize = maxSize;
this.element = new int[maxSize + 1];
Arrays.fill(element, Integer.MAX_VALUE);
this.size = 0;
}
@Override
public void add(int data) {
validateSizeAndResize();
this.element[++size] = data;
heapifyUpUseWhile(); // or heapifyUpUseFor();
}
// insert 할때는 마지막 인덱스부터 루트 인덱스(1) 까지 bottom-up 방식으로 크기를 비교해서 재구성 한다.
// min heap은 작은값이 부모가 되야한다.
private void heapifyUpUseFor() {
for (int i = size; i > 1; i--) {
int parentIndex = getParentIndex(i);
if (hasParent(i) && element[parentIndex] > element[i]) {
swap(parentIndex, i);
}
}
}
private void heapifyUpUseWhile() {
int childIndex = size;
while (hasParent(childIndex) && getParentData(childIndex) > element[childIndex]) {
swap(getParentIndex(childIndex), childIndex);
childIndex = getParentIndex(childIndex);
}
}
@Override
public int pop() {
if (size == 0) {
throw new ArrayIndexOutOfBoundsException("heap is empty");
}
int root = element[1];
element[1] = element[size];
element[size] = 0;
this.size = size - 1;
heapifyDownUseFor();// or heapifyDownUserWhile();
return root;
}
private void heapifyDownUseFor() {
for (int parent = 1; hasLeftChild(parent); ) {
if (parentValue(parent) < leftChildValue(parent) && parentValue(parent) < rightChildValue(parent)) {
break;
} else if (leftChildValue(parent) < rightChildValue(parent)) {
swap(parent, getLeftChildIndex(parent));
parent = parent * 2;
} else {
swap(parent, getRightChildIndex(parent));
parent = parent * 2 + 1;
}
}
}
// 자식 값중 더 작은 값을 교체해줘야 한다.
public void heapifyDownUserWhile() {
int parent = 1;
while (hasLeftChild(parent)) {
int smallIndex = smallerOfTheChildren(parent);
if (hasRightChild(parent) && rightChildValue(parent) < leftChildValue(parent)) {
smallIndex = getRightChildIndex(parent);
}
if (element[parent] < element[smallIndex]) {
break;
}
swap(parent, smallIndex);
parent = smallIndex;
}
}
private int smallerOfTheChildren(int parentIndex) {
if (hasLeftChild(parentIndex) && leftChildValue(parentIndex) < rightChildValue(parentIndex)) {
return getLeftChildIndex(parentIndex);
} else {
return getRightChildIndex(parentIndex);
}
}
@Override
public void printElements() {
if (this.size == 0) {
return;
}
while (!(this.size == 0)) {
System.out.print(pop() + ", ");
}
}
@Override
public boolean contains(int data) {
for (int i = 1; i <= size; i++) {
if (element[i] == data) {
return true;
}
}
return false;
}
@Override
public int peek() {
return element[1];
}
@Override
public int size() {
return this.size;
}
public static void main(String[] args) {
ArrayMinHeap arrayMinHeap = new ArrayMinHeap(10);
arrayMinHeap.add(5);
arrayMinHeap.add(4);
arrayMinHeap.add(2);
arrayMinHeap.add(7);
arrayMinHeap.add(8);
arrayMinHeap.add(9);
arrayMinHeap.add(3);
arrayMinHeap.add(6);
arrayMinHeap.add(15);
arrayMinHeap.add(999);
arrayMinHeap.add(2134134);
arrayMinHeap.add(21);
arrayMinHeap.add(1);
arrayMinHeap.add(9918324);
arrayMinHeap.add(239328);
arrayMinHeap.add(8237237);
arrayMinHeap.add(99999999);
arrayMinHeap.printElements();
}
}
[힙(Heap)](https://github.com/gyoogle/tech-interview-for-developer/blob/master/Computer Science/Data Structure/Heap.md)
[Data Structure] Heap](https://github.com/WooVictory/Ready-For-Tech-Interview/blob/master/Data Structure/[Data Structure] Heap.md)
[Binary Heap](