文章目录
1.堆的原理2.堆的代码实现3.堆排序（HeapSort）
1.堆的原理
堆排序与快速排序，归并排序一样都是时间复杂度为
O
(
n
l
o
g
n
)
O_(nlogn)
O(nlogn)的几种高级排序方法。学习堆排序前，先介绍一下数据结构中的二叉堆(BinaryHeap)。
二叉堆的定义 二叉堆是完全二叉树或者是近似完全二叉树。 二叉堆满足二个特性：
1．父结点的键值总是大于或等于任何一个子节点的键值。 2．每个结点的左子树和右子树都是一个二叉堆（都是最大堆）。
父子节点顺序定义公式
p
a
r
e
n
t
(
k
)
=
i
/
2
(
取
整
)
parent(k)=i/2(取整)
parent(k)=i/2(取整)
l
e
f
t
c
h
i
l
d
(
k
)
=
2
∗
k
left child(k)=2*k
leftchild(k)=2∗k
r
i
g
h
t
c
h
i
l
d
(
k
)
=
2
∗
k
+
1
right child(k)=2*k+1
rightchild(k)=2∗k+1最大堆存储示意图
堆的操作：入队(shift up) 堆的操作：出队(shift down) 下面先给出《数据结构C++语言描述》中最小堆的建立插入删除的图解
2.堆的代码实现
代码实战
#include <ctime>
#include <cmath>
#include <cassert>
#include <typeinfo>
#include "SortTestHelper.h"
using namespace std;
template<typename Item>
class MaxHeap{
private:
Item *data;
int count;
int capacity;
void shiftUp(int k){
//coss the border ;father node < child node
while( k > 1 && data[k/2] < data[k] ){
swap( data[k/2], data[k] );
k /= 2;
}
}
void shiftDown(int k){
while( 2*k <= count ){//k是有左孩子
int j = 2*k; // 在此轮循环中,data[k]和data[j]交换位置
if( j+1 <= count && data[j+1] > data[j] )// j+1 <= count有右孩子
j ++;
// data[j] 是 data[2*k]和data[2*k+1]中的最大值
if( data[k] >= data[j] ) break;//父亲节点大于孩子节点,break
swap( data[k] , data[j] );
k = j;//进行下一轮循环
}
}
public:
// 构造函数, 构造一个空堆, 可容纳capacity个元素
MaxHeap(int capacity){
data = new Item[capacity+1];
count = 0;
this->capacity = capacity;
}
// Heapify,构造函数, 通过一个给定数组创建一个最大堆
// 该构造堆的过程, 时间复杂度为O(n)
MaxHeap(Item arr[], int n){
data = new Item[n+1];
capacity = n;
for( int i = 0 ; i < n ; i ++ )//赋值给data
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;
}
// 像最大堆中插入一个新的元素 item
void insert(Item item){
assert( count + 1 <= capacity );//防止越界;其实可以new增加容量
data[count+1] = item;
count ++;
shiftUp(count);
}
// 从最大堆中取出堆顶元素, 即堆中所存储的最大数据
Item extractMax(){
assert( count > 0 );
Item ret = data[1];
swap( data[1] , data[count] );
count --;
shiftDown(1);//第一个元素向下移
return ret;
}
public:
// 以树状打印整个堆结构
void testPrint(){
// 我们的testPrint只能打印100个元素以内的堆的树状信息
if( size() >= 100 ){
cout<<"This print function can only work for less than 100 int";
return;
}
// 我们的testPrint只能处理整数信息
if( typeid(Item) != typeid(int) ){
cout <<"This print function can only work for int item";
return;
}
cout<<"The max heap size is: "<<size()<<endl;
cout<<"Data in the max heap: ";
for( int i = 1 ; i <= size() ; i ++ ){
// 我们的testPrint要求堆中的所有整数在[0, 100)的范围内
assert( data[i] >= 0 && data[i] < 100 );
cout<<data[i]<<" ";
}
cout<<endl;
cout<<endl;
int n = size();
int max_level = 0;
int number_per_level = 1;
while( n > 0 ) {
max_level += 1;
n -= number_per_level;
number_per_level *= 2;
}
int max_level_number = int(pow(2, max_level-1));
int cur_tree_max_level_number = max_level_number;
int index = 1;
for( int level = 0 ; level < max_level ; level ++ ){
string line1 = string(max_level_number*3-1, ' ');
int cur_level_number = min(count-int(pow(2,level))+1,int(pow(2,level)));
bool isLeft = true;
for( int index_cur_level = 0 ; index_cur_level < cur_level_number ; index ++ , index_cur_level ++ ){
putNumberInLine( data[index] , line1 , index_cur_level , cur_tree_max_level_number*3-1 , isLeft );
isLeft = !isLeft;
}
cout<<line1<<endl;
if( level == max_level - 1 )
break;
string line2 = string(max_level_number*3-1, ' ');
for( int index_cur_level = 0 ; index_cur_level < cur_level_number ; index_cur_level ++ )
putBranchInLine( line2 , index_cur_level , cur_tree_max_level_number*3-1 );
cout<<line2<<endl;
cur_tree_max_level_number /= 2;
}
}
private:
void putNumberInLine( int num, string &line, int index_cur_level, int cur_tree_width, bool isLeft){
int sub_tree_width = (cur_tree_width - 1) / 2;
int offset = index_cur_level * (cur_tree_width+1) + sub_tree_width;
assert(offset + 1 < line.size());
if( num >= 10 ) {
line[offset + 0] = '0' + num / 10;
line[offset + 1] = '0' + num % 10;
}
else{
if( isLeft)
line[offset + 0] = '0' + num;
else
line[offset + 1] = '0' + num;
}
}
void putBranchInLine( string &line, int index_cur_level, int cur_tree_width){
int sub_tree_width = (cur_tree_width - 1) / 2;
int sub_sub_tree_width = (sub_tree_width - 1) / 2;
int offset_left = index_cur_level * (cur_tree_width+1) + sub_sub_tree_width;
assert( offset_left + 1 < line.size() );
int offset_right = index_cur_level * (cur_tree_width+1) + sub_tree_width + 1 + sub_sub_tree_width;
assert( offset_right < line.size() );
line[offset_left + 1] = '/';
line[offset_right + 0] = '\\';
}
};
打印测试
3.堆排序（HeapSort）
算法步骤： （1）将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区； （2）将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]； （3）由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。算法图示： 堆排序&heapify优化排序代码实战
/ heapSort1, 将所有的元素依次添加到堆中, 在将所有元素从堆中依次取出来, 即完成了排序
// 无论是创建堆的过程, 还是从堆中依次取出元素的过程, 时间复杂度均为O(nlogn)
// 整个堆排序的整体时间复杂度为O(nlogn)
template<typename T>
void heapSort1(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();
}
// heapSort2, 借助我们的heapify过程创建堆
// 此时, 创建堆的过程时间复杂度为O(n), 将所有元素依次从堆中取出来, 实践复杂度为O(nlogn)
// 堆排序的总体时间复杂度依然是O(nlogn), 但是比上述heapSort1性能更优, 因为创建堆的性能更优
template<typename T>
void heapSort2(T arr[], int n){
MaxHeap<T> maxheap = MaxHeap<T>(arr,n);
for( int i = n-1 ; i >= 0 ; i-- )
arr[i] = maxheap.extractMax();
}
测试代码
// 测试 MaxHeap
int main() {
MaxHeap<int> maxheap = MaxHeap<int>(100);
srand(time(NULL));
for( int i = 0 ; i < 50 ; i ++ )
maxheap.insert( rand()0 );//[0,100)
maxheap.testPrint();
maxheap.extractMax();
// while( !maxheap.isEmpty()){
// cout<<maxheap.extractMax()<<endl;
// }
maxheap.testPrint();
int n = 1000000;
// 测试1 一般性测试
cout<<"Test for random array, size = "<<n<<", random range [0, "<<n<<"]"<<endl;
int* arr1 = SortTestHelper::generateRandomArray(n,0,n);
int* arr2 = SortTestHelper::copyIntArray(arr1, n);
SortTestHelper::testSort("Heap Sort 1", heapSort1, arr1, n);
SortTestHelper::testSort("Heap Sort 2", heapSort2, arr2, n);
delete[] arr1;
delete[] arr2;
cout<<endl;
// 测试2 测试近乎有序的数组
int swapTimes = 100;
cout<<"Test for nearly ordered array, size = "<<n<<", swap time = "<<swapTimes<<endl;
arr1 = SortTestHelper::generateNearlyOrderedArray(n,swapTimes);
arr2 = SortTestHelper::copyIntArray(arr1, n);
SortTestHelper::testSort("Heap Sort 1", heapSort1, arr1, n);
SortTestHelper::testSort("Heap Sort 2", heapSort2, arr2, n);
delete[] arr1;
delete[] arr2;
cout<<endl;
// 测试3 测试存在包含大量相同元素的数组
cout<<"Test for random array, size = "<<n<<", random range [0,10]"<<endl;
arr1 = SortTestHelper::generateRandomArray(n,0,10);
arr2 = SortTestHelper::copyIntArray(arr1, n);
SortTestHelper::testSort("Heap Sort 1", heapSort1, arr1, n);
SortTestHelper::testSort("Heap Sort 2", heapSort2, arr2, n);
delete[] arr1;
delete[] arr2;
return 0;
}
实验效果
