## 二叉堆

1. min-heap
The value of each node >= the value of its parent. Root is minimum-value element.
2. max-heap
The value of each node <= the value of its parent. Root is maximum-value element.

min-heap：

max-heap：

• 左子 index: 2 * k + 1
• 右子 index: 2 * k + 2
• 父 index: k-1 / 2（如果k为0，那么要特殊处理这一部分，因为 index = 0 时没有父节点）

## 优先队列——数组版

#pragma once
#include "datapoint.h"

class PQSortedArray {
public:

PQSortedArray();
~PQSortedArray();

void enqueue(DataPoint element);
DataPoint dequeue();
DataPoint peek() const;
bool isEmpty() const;
int size() const;

void clear();
void printDebugInfo();

private:
DataPoint* elements; // array of elements
int allocatedCapacity;  // number of slots allocated in array
int numItems;           // number of slots used in array

void validateInternalState();
void expand();

DISALLOW_COPYING_OF(PQSortedArray);
};



const int INITIAL_CAPACITY = 10;

PQSortedArray::PQSortedArray() {
numItems = 0;
allocatedCapacity = INITIAL_CAPACITY;
elements = new DataPoint[allocatedCapacity];
}

PQSortedArray::~PQSortedArray() {
delete[] elements;
}

void PQSortedArray::enqueue(DataPoint elem) {
if(allocatedCapacity == numItems){
expand();
}

int index = 0;

for(int i = 0; i < numItems - 1; i++){
if(elem.priority <= elements[i].priority && elem.priority >= elements[i+1].priority){
index = i + 1;
break;
}
}

if(!isEmpty() && elem.priority < elements[numItems - 1].priority){
index = numItems;
}

for(int i = numItems; i > index; i--){
elements[i] = elements[i-1];
}
elements[index] = elem;

numItems++;

validateInternalState();
}

int PQSortedArray::size() const {
return numItems;
}

DataPoint PQSortedArray::peek() const {
if (isEmpty()) {
error("Cannot peek empty pqueue");
}
int lastOccupiedSlot = numItems - 1;
return elements[lastOccupiedSlot];
}

DataPoint PQSortedArray::dequeue() {
if (isEmpty()) {
error("Cannot deqeuue empty pqueue");
}
int lastOccupiedSlot = numItems - 1;
numItems--;
return elements[lastOccupiedSlot];
}

bool PQSortedArray::isEmpty() const {
return size() == 0;
}

void PQSortedArray::clear() {
numItems = 0;
}

void PQSortedArray::printDebugInfo() {
for (int i = 0; i < size(); i++) {
cout << "[" << i << "] = " << elements[i] << endl;
}
}

void PQSortedArray::validateInternalState(){
if (size() == 0 || size() == 1){
return;
}

if (size() > allocatedCapacity) error("Too many elements in not enough space!");

DataPoint lastElem = elements[0];
for (int i = 1; i < size(); i++){
DataPoint cur = elements[i];
if (cur.priority > lastElem.priority){
error("Internal state of the array is out of order!");
}
lastElem = cur;
}
}

void PQSortedArray::expand(){
DataPoint* newElements = new DataPoint[allocatedCapacity * 2];
for(int i = 0; i < numItems; ++i){
newElements[i] = elements[i];
}
delete elements;
elements = newElements;
allocatedCapacity *= 2;
}


## 优先队列——二叉堆

class PQHeap {
public:

PQHeap();
~PQHeap();

void enqueue(DataPoint element);
DataPoint dequeue();
DataPoint peek() const;
bool isEmpty() const;
int size() const;
void clear();
void printDebugInfo();

private:
DataPoint* elements;
int allocatedCapacity;
int numItems;

void expand();
void validateInternalState();

int getParentIndex(int curIndex);
int getLeftChildIndex(int curIndex);
int getRightChildIndex(int curIndex);

DISALLOW_COPYING_OF(PQHeap);
};


const int INITIAL_CAPACITY = 10;

PQHeap::PQHeap() {
elements = new DataPoint[INITIAL_CAPACITY];
allocatedCapacity = INITIAL_CAPACITY;
numItems = 0;
}

PQHeap::~PQHeap() {
delete [] elements;
}

void PQHeap::enqueue(DataPoint elem) {
if(numItems == allocatedCapacity){
expand();
}

elements[numItems] = elem;
int parentIndex = getParentIndex(numItems);
int previousIndex = numItems;

while(parentIndex != -1){ //-1 means no parent index
if(elem.priority >= elements[parentIndex].priority){
break;
}else{
DataPoint tmp = elements[parentIndex];
elements[parentIndex] = elements[previousIndex];
elements[previousIndex] = tmp;
previousIndex = parentIndex;
parentIndex = getParentIndex(previousIndex);
}
}

numItems++;
validateInternalState();
}

DataPoint PQHeap::peek() const {
if(isEmpty()){
error("Queue is empty!");
}

return elements[0];
}

DataPoint PQHeap::dequeue() {
if(isEmpty()){
error("Queue is empty!");
}

DataPoint dp = elements[0];
elements[0] = elements[numItems - 1];
numItems--;

int leftChildIndex = getLeftChildIndex(0);
int rightChildIndex = getRightChildIndex(0);
int previousIndex = 0;

while(leftChildIndex < numItems){
int priority = elements[previousIndex].priority;
int leftPriority = elements[leftChildIndex].priority;

if(rightChildIndex < numItems){
int rightPriority = elements[rightChildIndex].priority;
if(priority > leftPriority || priority > rightPriority){
if(leftPriority < priority && leftPriority < rightPriority){
DataPoint tmp = elements[previousIndex];
elements[previousIndex] = elements[leftChildIndex];
elements[leftChildIndex] = tmp;
previousIndex = leftChildIndex;
rightChildIndex = getRightChildIndex(previousIndex);
leftChildIndex = getLeftChildIndex(previousIndex);
}else{
DataPoint tmp = elements[previousIndex];
elements[previousIndex] = elements[rightChildIndex];
elements[rightChildIndex] = tmp;
previousIndex = rightChildIndex;
leftChildIndex = getLeftChildIndex(previousIndex);
rightChildIndex = getRightChildIndex(previousIndex);
}
}else{
break;
}
}
else{
if(leftPriority < priority){
DataPoint tmp = elements[previousIndex];
elements[previousIndex] = elements[leftChildIndex];
elements[leftChildIndex] = tmp;
}
break;
}
}

validateInternalState();

return dp;
}

bool PQHeap::isEmpty() const {
return numItems == 0;
}

int PQHeap::size() const {
return numItems;
}

void PQHeap::clear() {
numItems = 0;
}

void PQHeap::printDebugInfo() {
for (int i = 0; i < size(); i++) {
cout << "[" << i << "] = " << elements[i] << endl;
}
}

void PQHeap::validateInternalState(){
if (size() == 0 || size() == 1){
return;
}

if (size() > allocatedCapacity) error("Too many elements in not enough space!");

for (int i = 1; i < size(); i++){
DataPoint cur = elements[i];
DataPoint parent = elements[getParentIndex(i)];

if(getLeftChildIndex(i) < numItems){
DataPoint leftChildren = elements[getLeftChildIndex(i)];

if(getRightChildIndex(i) < numItems){
DataPoint rightChildren = elements[getRightChildIndex(i)];
if(cur.priority > leftChildren.priority || cur.priority > rightChildren.priority){
error("The queue is out of order!1");
}
}else{
if(cur.priority > leftChildren.priority){
error("The queue is out of order!");
}
}
}
if(cur.priority < parent.priority){
error("The queue is out of order!");
}
}
}

int PQHeap::getParentIndex(int curIndex){
if(curIndex == 0) return -1;
return (curIndex - 1)/2;
}

int PQHeap::getLeftChildIndex(int curIndex){
return 2*curIndex + 1;
}

int PQHeap::getRightChildIndex(int curIndex){
return 2*curIndex + 2;
}

void PQHeap::expand(){
DataPoint* newElements = new DataPoint[allocatedCapacity * 2];
for(int i = 0; i < numItems; ++i){
newElements[i] = elements[i];
}
delete elements;
elements = newElements;
allocatedCapacity *= 2;
}