摘要：
简介 当二叉树的每个节点大于其两个子节点时，称为堆顺序；如果我们使用指针来表示一个堆排序的二叉树，那么每个元素都需要三个指针来查找其上下节点；但如果我们使用一个完整的二叉树，它只能用没有指针的数组来表示；最小堆是多少？最小堆基于二进制堆，并且符合每个节点小于其子节点的规则！size:DefaultSize；｝MinHeap:：~MinHeap（）｛｝voidMinHeap：：toString（）{用于｛std:：cout＜＜heap[i]＜＜std:：endl；｝｝voidMinHeap:：swap｛inttemp=*num1；*num1=*num2；*num2=temp；｝/****从开始到结束删除数据*将子节点与父节点进行比较**@paramstart＜#startdescription#＞*@param＜#enddescription#＞*/voidMinHeap:：shiftDown｛inti=start；而｛intlchild=i*2+1，archive=i*2+2；如果{bootleftSmall=头[lchild]0）｛int parent=i%2==0？
当一棵二叉树的每个结点都大于它的两个子结点时，被称为堆有序；
如果我们用指针来表示堆有序的二叉树，那么每个元素都需要三个指针来找到它的上下结点；但是如果我们使用完全二叉树，只用数组而不需要指针就可以表示；
什么是最小堆呢？
最小堆就是在二叉堆的基础上，符合了每个结点都比他的子结点要小的规则！
我们会遇到这两种情况，这也是最小堆中特别要注意的两种实现：
- 上浮：从下至上恢复堆的顺序，在当某个节点的优先级上升时；
- 下沉：从上至下恢复的顺序，当某个节点的优先级下降的时候；
我们可以从下面的图中观察最小堆是如何运行的：
只要不满足小的规则就交换
实现1.上浮
先看上浮，其思想就是，因为是从下至上，所以根据当前结点，算出父亲结点，然后跟父亲结点进行比较，如果子结点小的话，则需要进行相互交换，反之不用，直到循环到下标到达结尾；
/**
* 将end到0的数据都上浮
*
* @param end
*/
void MinHeap::shiftUp(int end) {
int i = end;
while (i > 0) {
int parent = i % 2 == 0 ? i/2 - 1 : i/2;
if (heap[i] < heap[parent]) {
swap(&heap[i], &heap[parent]);
i = parent;
}
else {
--i;
}
}
}
2.下沉
接着看下沉，其思想就是，因为是从上至下，所以根据当前结点，算出左右子结点，然后跟当前结点进行比较，如果左右结点小，这里需要注意的是，取左右子结点中小的进行交换，因为其中必然会有三者之中的最小值，反之不用，直到循环到下标到达0；
/**
* 将start到end的数据都往下沉
* 将子结点和父结点进行比较
*
* @param start <#start description#>
* @param end <#end description#>
*/
void MinHeap::shiftDown(int start, int end) {
int i = start;
while (i < end) {
int lchild = i*2 + 1, rchild = i*2 + 2;
if ((heap[i] > heap[lchild] && lchild < currentSize) || (heap[i] > heap[rchild] && rchild < currentSize)) {
bool leftSmall = heap[lchild] < heap[rchild];
if (leftSmall) {
swap(&heap[i], &heap[lchild]);
i = lchild;
}
else {
swap(&heap[i], &heap[rchild]);
i = rchild;;
}
}
else {
++i;
}
}
}
3.插入删除
还有一个需要注意的点是插入删除；
- 插入：插到数组的最后一个位置上，增加堆大小，并且上浮；
- 删除：将数组头元素用数组尾元素进行替换，减小堆大小，并且下沉；
4.整体实现
//
// main.cpp
// Heap
//
// Created by George on 16/11/1.
// Copyright © 2016年 George. All rights reserved.
//
#include <iostream>
#define DefaultSize 10
#define Log(content) { std::cout << "Log:" << content << std::endl; }
class MinHeap {
public:
MinHeap(int size = DefaultSize);
~MinHeap();
inline bool isEmpty() {
return currentSize == 0;
};
inline bool isFull() {
return currentSize == maxSize;
};
bool insert(const int value);
bool removeMin();
int poll();
void shiftDown(int start, int end);
void shiftUp(int end);
void toString();
private:
int * heap;
int currentSize;
int maxSize;
void swap(int *num1, int *num2);
};
MinHeap::MinHeap(int size) : currentSize(0) {
heap = new int[size];
maxSize = size > DefaultSize ? size : DefaultSize;
}
MinHeap::~MinHeap() {
}
void MinHeap::toString() {
for (int i = 0; i < currentSize; ++i) {
std::cout << heap[i] << std::endl;
}
}
void MinHeap::swap(int *num1, int *num2) {
int temp = *num1;
*num1 = *num2;
*num2 = temp;
}
/**
* 将start到end的数据都往下沉
* 将子结点和父结点进行比较
*
* @param start <#start description#>
* @param end <#end description#>
*/
void MinHeap::shiftDown(int start, int end) {
int i = start;
while (i < end) {
int lchild = i*2 + 1, rchild = i*2 + 2;
if ((heap[i] > heap[lchild] && lchild < currentSize) || (heap[i] > heap[rchild] && rchild < currentSize)) {
bool leftSmall = heap[lchild] < heap[rchild];
if (leftSmall) {
swap(&heap[i], &heap[lchild]);
i = lchild;
}
else {
swap(&heap[i], &heap[rchild]);
i = rchild;;
}
}
else {
++i;
}
}
}
/**
* 将end到0的数据都上浮
*
* @param end
*/
void MinHeap::shiftUp(int end) {
int i = end;
while (i > 0) {
int parent = i % 2 == 0 ? i/2 - 1 : i/2;
if (heap[i] < heap[parent]) {
swap(&heap[i], &heap[parent]);
i = parent;
}
else {
--i;
}
}
}
/**
* 删除最小值，也就是堆顶，用最大值替代，并且下沉
*
* @return <#return value description#>
*/
bool MinHeap::removeMin() {
if (currentSize == 0) {
Log("current size is 0!");
return false;
}
heap[0] = heap[currentSize-1];
--currentSize;
shiftDown(0, currentSize-1);
return true;
}
/**
* 插入值后要进行上浮
*
* @param value <#value description#>
*
* @return <#return value description#>
*/
bool MinHeap::insert(const int value) {
if (currentSize == maxSize) {
int *nHeap = heap;
heap = new int(maxSize + 10);
for (int i = 0; i < maxSize; ++i) {
heap[i] = nHeap[i];
}
delete [] nHeap;
Log("heap is resize!");
}
heap[currentSize++] = value;
shiftUp(currentSize-1);
return true;
}
/**
* 取得堆顶值
*
* @return <#return value description#>
*/
int MinHeap::poll() {
if (isEmpty()) {
Log("heap is null!");
return -1;
}
return heap[0];
}
int main(int argc, const char * argv[]) {
// insert code here...
MinHeap Heap;
Log("------------Insert------------");
int arr[8] = {8, 7, 6, 5, 4, 3, 2, 1};
for (int i = 0; i < 8; i++) {
Heap.insert(arr[i]);
}
Heap.toString();
Log("------------Remove------------");
Heap.removeMin();
Heap.toString();
Log("------------Get------------");
std::cout << "poll:" << Heap.poll() << std::endl;
return 0;
}
看结果：