梅庄

算法回顾---堆排序

发表于 | 分类于
堆排序

Heap Sort

普通队列：先进先出；后进后出
优先队列：出队顺序和入队顺序无关；和优先级有关
如操作系统每次动态选择优先级最高的任务执行
人工智能中选择当前要攻击的对象
在1,000,000个元素中选出前100名（在N个元素中选出个元素）
1) 先排序（NlogN)
2) 使用优先队列（NlogM)
优先队列主要操作
1）入队
2）出队（取出优先级最高的元素）

堆的实现

不意味着层数越高，数值越大

用数组存储二叉堆

父节点下标i（从1开始）
左子结点下标2i，右子结点下标2i+1
parent(i) = i / 2
left child(i) = 2i
right child(i) = 2i+1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
template<typename Item>
class MaxHeap{
	
private:
	Item* data;
	int count;
	int capacity;
public:
	MaxHeap(int capacity){
		
		data = new Item[capacity+1];
		count = 0;
		this->capacity = capacity;
	}
	
	~MaxHeap(){
		delete[] data; 
	} 
	
	int size(){
		return count;
	}
	
	bool isEmpty(){
		return count == 0;
	}
	
	void insert(Item item){
		
		assert(count + 1 <= capacity);	//可实现，当发现容量不足的时候开辟新空间 
		data[count+1] = item;
		count++;
		shiftUp(count);
	}
}

Shift Up

新添加一个元素到最后
count++
将最后一个元素一步一步向上挪

1
2
3
4
5
6
7
void shiftUp(int k){
	
	while( k > 1 && data[k/2] < data[k] ){
		swap(data[k/2], data[k]);
		k /= 2;
	}
}

1
2
3
4
5
6
7
void insert(Item item){
	
	assert(count + 1 <= capacity);	//可实现，当发现容量不足的时候开辟新空间 
	data[count+1] = item;
	count++;
	shiftUp(count);
}

Shift Down

拿出根元素
把最后一个元素拿到根结点
将根结点一步一步向下挪

1
2
3
4
5
6
7
8
9
10
11
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++;	//如果右孩子大，那交换右孩子，否则交换左孩子 
		
		if(data[k] >= data[j])	break;
		
		swap( data[k], data[j] );	//swap可以用赋值操作优化，不用每次swap 
		k = j;
	}
}

1
2
3
4
5
6
7
8
9
Item extracrMax(){
	
	assert( count > 0 );
	Item ret = data[1];
	swap( data[1], data[count] );
	count--;
	shiftDown( 1 );
	return ret;
}

堆排序版本1

1
2
3
4
5
6
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.extracrMax();
}

堆排序版本2(Heapify)

给定一个数组，让这个数组组成堆的形状（heapify，快速建堆)
快速建堆
对于一个完全二叉树，第一个非叶子结点的索引下标（元素个数/2）
从后向前考察每一个非叶子结点

1
2
3
4
5
6
7
MaxHeap(Item arr[], int n){
	data = new Item[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);
}

1
2
3
4
5
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.extracrMax();
}

系统级别数据很少用堆排序
堆排序主要用于动态数据的维护
为什么建堆快？
因为：
将n各元素逐个插入到一个空堆中O(nlogn)
heapify的过程，复杂度O(n)

原地堆排序（空间O(1)复杂度）

先heapify建堆，取出首元素（最大），与最后元素交换
元素个数减一，将首元素调整，重新调整堆，将首元素与最后元素交换
……
此过程依次类推

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
// 堆是完全二叉树，第1个结点存储于数组中的1号位，第i号结点的左儿子为2*i,右儿子为2*i+1
const int maxn = 100;
// heap为堆，n为元素个数
int heap[maxn], n;
// 对heap数组在[low,high]范围内进行向下调整
// 其中low为预调整结点的数组下标，high一般为堆的最后一个元素的数组下标
void percolateDown(int low, int high)
{
    int i = low, j = i*2;   //i为调整结点，j为左孩子
    while(j <= high)
    {
        // 注意：要先保证heap[j+1]存在
        if(heap[j] < heap[j+1]) j=j+1;  //选左右孩子中大的哪一个
        // 将heap[i]向下调整
        if(heap[j] > heap[i])
        {
            swap(heap[i], heap[j]);
            i = j;
            j = i*2;
        }
        // heap[i]比两个孩子都大，跳出
        else
        {
            break;
        }
    }
}
// 建堆：自底向上逐步percolateDown
void creteHeap()
{
    for(int i = n/2; i>=1; i--)
    {
        percolateDown(i, n);
    }
}
// 删除堆顶元素
// 最后一个元素覆盖堆顶元素，同时元素个数减一，将堆顶元素逐步percolateDown
void deleteTop()
{
    heap[1] = heap[n--];
    percolateDown(1, n);
}
// 往堆里面添加一个元素，在最后添加，然后逐步percolateUp，直到父元素大于两个孩子
// 对heap数组在[low,high]范围percolateUp
// 其中low一般设置为1，high表示欲调整结点的数组下标
void percolateUp(int low, int high)
{
    int i = high, j = i/2;
    while(j >= low)
    {
        if(heap[j] < heap[i])
        {
            swap(heap[j], heap[i]);
            i = j;
            j = i /2;
        }
        else
        {
            break;
        }
    }
}
// 添加元素x
// 将待添加元素加入堆的末尾，然后逐步percolateUp,直到父元素比自己大为止
void insert(int x)
{
    heap[++n] = x;
    percolateUp(1, n);
}
// 堆排序  倒着遍历数组
// 先建堆，取出堆顶元素，将最后一个元素替换至堆顶，然后逐步percolateDown
// 一直重复，直到堆中只有一个元素为止
void heapSort()
{
    creteHeap();
    for(int i = n; i>1; i--)
    {
        swap(heap[1], heap[i]);
        percolateDown(1,i-1);
    }
}

排序算法总结

插入排序，当数组几乎有序的情况，插入排序会变成O（N）
快速排序，当在极特殊的情况下，快速排序会退化到O（N^2) (用随机化，使得退化的可能变得极地)
快速排序在O（nlogn）排序中常数占优
在右大量重复元素的情况下用三路归并排序
（原地排序：是否可以直接在原数组中排序）
快排空间（nlogn):因为采用递归的方法 ，递归过程有logn层，需要logn层的栈空间

比如先按字典序排序，稳定排序可以保证：按成绩排序之后，相同成绩的学生仍然按名字的字典序来排序

排序的稳定性和实现方法有关，如果实现不好的话，会将插入排序和归并排序实现为不稳定的排序