关于树和二叉树介绍以及遍历可以查看之前写的两篇文章
树的简单介绍和二叉树的遍历
二叉树
最大堆和最小堆
最大堆：根结点的键值是所有堆结点键值中最大者，且每个结点的值都比其孩子的值大。
最大堆.png
最小堆：根结点的键值是所有堆结点键值中最小者，且每个结点的值都比其孩子的值小。
最小堆.png
堆总是一颗完全二叉树
数组存储最大堆
image.png
此时父节点 parent(i)=i/2;
left child(i)=2i;
right child(i)=2i+1;
插入数据的时候需要将大的值往上浮，这时候我们需要一个shiftUp(上浮)操作，简单说比如插入一个52的值，首先我们把它放上去
image.png
这时候，52比16大，所以52和16交换位置，之后52与它的父节点41比较，因为52>41所以再次交换位置
image.png
void shiftUp(int k) {
while (k > 1 && data[k / 2] < data[k]) {
std::swap(data[k / 2], data[k]);
k /= 2;
}
}
//算法复杂度O(nlogn)
void insert(E e) {
assert(count + 1 <= capacity);
data[count + 1] = e;
count++;
shiftUp(count);
}
取出元素
最大堆取出元素取出的是最大的元素，也就是最大堆中的根节点，也就是上图的62这个元素，取出之后需要将最后一个元素，也就是上图的16放到62的位置，原本16的位置设置null,然后这时候要保持最大堆性质就需要进行shiftDown操作
image.png
首先16和52与30判断，我们会发现，16比它们都小，这时候，我们判读左右节点，我们会发现52>30，所以52和16交换，依次轮推，16会再次与41交换
image.png
void shiftDown(int k) {
while (2 * k <= count) {
int j = 2 * k;//在此轮循中，data[k]和data[j]交换位置
if (j + 1 <= count && data[j + 1] > data[j]) {
j += 1;
}
if (data[k] >= data[j]) {
break;
}
swap(data[k], data[j]);
k = j;
}
}
E extractMax() {
assert(count > 0);
E e = data[1];
swap(data[1], data[count]);
count--;
shiftDown(1);
return e;
}
Heapify:对已有的数组进行shiftDown
image.png
Heapify过程呢，其实就是倒着shiftDown的过程。比如上图所有蓝色的点，实际它们就是一个最大堆性质了，首先我们找到最后一个叶子结点的位置(n/2),这里实际就是10/2=5这个位置，因为5这个位置的值是22<62所以交换位置，第4位置和第8，9位置比较，因为13<30<41，所以41和13交换位置，剩下依次推论就可以了
image.png
最后结果.png
//Heapify的过程，算法复杂度O(n)
MaxHeap(E arr[], int n) {
data = new E(n + 1);
capacity = n;
for (int i = 0; i < n; ++i) {
data[i + 1] = arr[i];
}
count = n;
for (int i = count / 2; i >= 1; i--) {
shiftDown(i);
}
}
一般排序方式
template<class T>
void headSort1(T arr[], int n) {
MaxHeap<T> maxHeap = MaxHeap<T>(n);
for (int i = 0; i < n; ++i) {
maxHeap.insert(arr[i]);
}
//从小到大
for (int i = n - 1; i >= 0; i--) {
arr[i] = maxHeap.extractMax();
}
}
template<class T>
void headSort2(T arr[], int n) {
MaxHeap<T> maxHeap = MaxHeap<T>(arr, n);
//从小到大
for (int i = n - 1; i >= 0; i--) {
arr[i] = maxHeap.extractMax();
}
}
//Heapify的过程，算法复杂度O(n)
MaxHeap(E arr[], int n) {
data = new E(n + 1);
capacity = n;
for (int i = 0; i < n; ++i) {
data[i + 1] = arr[i];
}
count = n;
for (int i = count / 2; i >= 1; i--) {
shiftDown(i);
}
}
E extractMax() {
assert(count > 0);
E e = data[1];
swap(data[1], data[count]);
count--;
shiftDown(1);
return e;
}
原地堆排序
上述代码我们不难发现，我们对原数组排序的时候开辟了一块内存空间，其实我们完全可以在原地(不开辟内存空间)进行排序
image.png
parent(i)=(i-1)/2
left child(i)=2i+1;
right child(i)=2i+2
其实就是shiftDown+heapify操作，只是这里的i是从0开始而不是从1开始
template<class T>
void _shiftDown(T arr,int n,int k){
while (2 * k+1<= n) {
int j = 2 * k+1;//在此轮循中，data[k]和data[j]交换位置
if (j + 1 <= n && arr[j + 1] > arr[j]) {
j += 1;
}
if (arr[k] >= arr[j]) {
break;
}
swap(arr[k], arr[j]);
k = j;
}
}
//原地排序
template<class T>
void headSort(T arr[], int n) {
//第一个非叶子结点的索引
for (int i = (n - 1) / 2; i >= 0; i--) {
_shiftDown(arr, n, i);
}
for (int i = n - 1; i > 0; i--) {
swap(arr[0], arr[i]);
_shiftDown(arr,i, 0);
}
完整代码
#ifndef NDK_PRIORITYQUEUE_H
#define NDK_PRIORITYQUEUE_H
#include <iostream>
#include <algorithm>
#include <string>
#include <ctime>
#include <cmath>
#include <cassert>
#define TAG "TAG"
#define LOGE(...) __android_log_print(ANDROID_LOG_ERROR,TAG,__VA_ARGS__)
//在n个元素选出前M个元素 优先队列nlogn 出队：选出优先级最高的
using namespace std;
template<class E>
class MaxHeap {
private:
E *data;
int count;
int capacity;
void shiftUp(int k) {
while (k > 1 && data[k / 2] < data[k]) {
std::swap(data[k / 2], data[k]);
k /= 2;
}
}
void shiftDown(int k) {
while (2 * k <= count) {
int j = 2 * k;//在此轮循中，data[k]和data[j]交换位置
if (j + 1 <= count && data[j + 1] > data[j]) {
j += 1;
}
if (data[k] >= data[j]) {
break;
}
swap(data[k], data[j]);
k = j;
}
}
public:
MaxHeap(int capacity) {
this->capacity = capacity;
data = new E[capacity + 1];
count = 0;
}
//Heapify的过程，算法复杂度O(n)
MaxHeap(E arr[], int n) {
data = new E(n + 1);
capacity = n;
for (int i = 0; i < n; ++i) {
data[i + 1] = arr[i];
}
count = n;
for (int i = count / 2; i >= 1; i--) {
shiftDown(i);
}
}
~MaxHeap() {
delete[] data;
}
int size() {
return count;
}
bool isEmpty() {
return count == 0;
}
//算法复杂度O(nlogn)
void insert(E e) {
assert(count + 1 <= capacity);
data[count + 1] = e;
count++;
shiftUp(count);
}
E extractMax() {
assert(count > 0);
E e = data[1];
swap(data[1], data[count]);
count--;
shiftDown(1);
return e;
}
};
template<class T>
void _shiftDown(T arr,int n,int k){
while (2 * k+1<= n) {
int j = 2 * k+1;//在此轮循中，data[k]和data[j]交换位置
if (j + 1 <= n && arr[j + 1] > arr[j]) {
j += 1;
}
if (arr[k] >= arr[j]) {
break;
}
swap(arr[k], arr[j]);
k = j;
}
}
//原地排序
template<class T>
void headSort(T arr[], int n) {
//第一个非叶子结点的索引
for (int i = (n - 1) / 2; i >= 0; i--) {
_shiftDown(arr, n, i);
}
for (int i = n - 1; i > 0; i--) {
swap(arr[0], arr[i]);
_shiftDown(arr,i, 0);
}
}
template<class T>
void headSort1(T arr[], int n) {
MaxHeap<T> maxHeap = MaxHeap<T>(n);
for (int i = 0; i < n; ++i) {
maxHeap.insert(arr[i]);
}
//从小到大
for (int i = n - 1; i >= 0; i--) {
arr[i] = maxHeap.extractMax();
}
}
template<class T>
void headSort2(T arr[], int n) {
MaxHeap<T> maxHeap = MaxHeap<T>(arr, n);
//从小到大
for (int i = n - 1; i >= 0; i--) {
arr[i] = maxHeap.extractMax();
}
}
#endif // NDK_PRIORITYQUEUE_H
网友评论