• 主页
  • 随笔
所有文章 友链 关于我

  • 主页
  • 随笔

排序算法08:优先队列与堆排序

2017-05-01

  堆排序一种是基于二叉堆的排序。本文将从优先队列讲起,循序渐进的实现堆排序。这也是《算法》第四版上讲解堆排序的大致章节结构。另外,本文所有的图都来自于此书。

优先队列

  普通队列是一种先进先出的数据结构,先放进队列的元素取值时优先被取出来。而优先队列是一种具有最高优先级元素先出的数据结构,比如每次取值都取最大的元素。

  优先队列有两个核心方法,一个是insert(val)向队列中添加元素,另外一个是delMax()删除最大元素(优先级最高的)并返回。可以考虑使用数组来存储优先队列的数据。

优先队列有如下三种实现方式:

  1. 有序数组(调用insert方法时使用类似插入排序把新增元素放到正确位置,调用delMax方法时直接取数组最后一个元素,因为此时元素已经是有序状态)
  2. 无序数组(调用insert方法时直接把元素放到数组中,调用dexMax方法时使用类似选择排序的方法从数组中找出最大元素,删除并返回)
  3. 堆

堆的算法

  优先队列可以使用一棵堆有序的二叉树来解决。什么叫做堆有序呢?当一棵二叉树的每个几点都大于它的两个子节点时,它被称为堆有序。那么,根节点就是堆有序的二叉树中的最大节点。

  二叉堆可以使用数组来存储。为了方便起见,根节点放在位置1处(位置0不使用),它的两个子节点分别放在位置2和位置3。同理可知,在一个堆中,位置k的节点的父节点的位置为k/2,而它的两个子节点的位置则分别为2k和2k+1.我们就可以这样在树的上下移动:访问a[k]节点的上一层就令k等于k/2,向下一层就令k等于2k或2k+1.

如下图所示:

  使用二叉堆,我们就能实现对数级别的插入元素和删除最大元素。

由下自上的堆有序化(上浮)

  当调用优先队列的insert方法时,我们首先把元素放置到数组的结尾,然后再把该元素上浮到正确的节点,最终形成堆有序状态。

代码如下:

1
2
3
4
5
6
7
8
9
//下标为k的元素上浮到正确位置
function swim(arr,k) {
while(k>1 && less(arr,parseInt(k/2),k)){
//父节点索引
var parentNode = parseInt(k/2);
exch(arr,parentNode,k);
k = parentNode;
}
}

由上至下的堆有序化(下沉)

  当调用优先队列的delMax方法时,我们下标为1的元素(最大元素)和数组最后一个元素交换,返回最大元素,数组长度减去1,即删除最后一个元素。此时的位置1元素不一定是最大元素,就需要下沉到正确位置,重新构造有序堆。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
//下标为k的元素下沉到正确位置
function sink(arr,k,len) {
var len = len ||arr.length;
while(2*k <= len){
var j = 2*k;
if(j<len && less(arr,j,j+1)) j++;
if(!less(arr,k,j)) break;
exch(arr,k,j);
k = j;
}
}

堆有序化示例图:

堆的操作示例图:

优先队列实现

  理解了实现堆有序的上浮和下沉两种方法,优先队列的实现就轻而易举了,代码如下:

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
/**
* 优先队列
* @constructor
*/
function MaxQueue() {
this.queue = []; //- 存储基于堆的完全二叉树
this.len = 0; //- 存储于queue[1..len]中,queue[0]未使用
}

/**
* 向优先队列中插入元素
* @param val
*/
MaxQueue.prototype.insert = function (val) {
this.queue[++this.len] = val; //- 从索引1开始添加元素
//使新增元素上浮到树的正确位置
swim(this.queue,this.len);
};

/**
* 删除优先队列中的最大元素,并返回该元素
* @returns {*}
*/
MaxQueue.prototype.delMax = function () {
var max = this.queue[1]; //- 从根节点得到最大元素
exch(this.queue,1,this.len--); //- 把最后一个节点放到根节点上,并且让长度索引减一
this.queue.length = this.len+1; //- 删除最后一个节点
sink(this.queue,1); //- 下沉根节点,恢复堆的有序性
return max;
};

MaxQueue.prototype.show = function () {
console.log(this.queue);
};

MaxQueue.prototype.isEmpty = function () {
return this.len==0;
};

示例图:

堆排序

  理解了优先队列,堆排序的逻辑十分简单。第一步:让数组形成堆有序状态;第二步:把堆顶的元素放到数组最末尾,末尾的放到堆顶,在剩下的元素中下沉到正确位置,重复操作即可。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
* 堆排序算法
* @constructor
*/
function HeapSort() {}
HeapSort.prototype.sort = function (arr) {
var len = arr.length;
//由于arr[0]不使用,放到最后使得能够被排序
//注意:也可在less和exch中解决,见后面的Java完整代码实现。这里为了对应位置1的元素不使用,方便对照看代码与样例图。
arr[len] = arr[0];
//使用下沉来构造二叉堆
for(var k=parseInt(len/2);k>=1;k--){
sink(arr,k,len);
}
//不断把最大的arr[1]交换到最后,然后让新的arr[1]元素下沉到堆有序状态
while (len>1){
exch(arr,1,len--);
sink(arr,1,len);
}
//删除未使用的arr[0](也可在less和exch中解决,见Java代码实现)
arr.splice(0,1);
};

示例图:

完整代码

Javascript实现

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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
/**
* Created by YiYing on 2017/5/2.
*/
(function (W) {

/**
* 优先队列
* @constructor
*/
function MaxQueue() {
this.queue = []; //- 存储基于堆的完全二叉树
this.len = 0; //- 存储于queue[1..len]中,queue[0]未使用
}

/**
* 向优先队列中插入元素
* @param val
*/
MaxQueue.prototype.insert = function (val) {
this.queue[++this.len] = val; //- 从索引1开始添加元素
//使新增元素上浮到树的正确位置
swim(this.queue,this.len);
};

/**
* 删除优先队列中的最大元素,并返回该元素
* @returns {*}
*/
MaxQueue.prototype.delMax = function () {
var max = this.queue[1]; //- 从根节点得到最大元素
exch(this.queue,1,this.len--); //- 把最后一个节点放到根节点上,并且让长度索引减一
this.queue.length = this.len+1; //- 删除最后一个节点
sink(this.queue,1); //- 下沉根节点,恢复堆的有序性
return max;
};

MaxQueue.prototype.show = function () {
console.log(this.queue);
};

MaxQueue.prototype.isEmpty = function () {
return this.len==0;
};

W.MaxQueue = MaxQueue;


/**
* 堆排序算法
* @constructor
*/
function HeapSort() {}
HeapSort.prototype.sort = function (arr) {
var len = arr.length;
//由于arr[0]不使用,放到最后使得能够被排序
//注意:也可在less和exch中解决,见后面的Java完整代码实现。这里为了对应位置1的元素不使用,方便对照看代码与样例图。
arr[len] = arr[0];
//使用下沉来构造二叉堆
for(var k=parseInt(len/2);k>=1;k--){
sink(arr,k,len);
}
//不断把最大的arr[1]交换到最后,然后让新的arr[1]元素下沉到堆有序状态
while (len>1){
exch(arr,1,len--);
sink(arr,1,len);
}
//删除未使用的arr[0](也可在less和exch中解决,见Java代码实现)
arr.splice(0,1);
};

W.HeapSort = HeapSort;


//下标为k的元素上浮到正确位置
function swim(arr,k) {
while(k>1 && less(arr,parseInt(k/2),k)){
//父节点索引
var parentNode = parseInt(k/2);
exch(arr,parentNode,k);
k = parentNode;
}
}

//下标为k的元素下沉到正确位置
function sink(arr,k,len) {
var len = len ||arr.length;
while(2*k <= len){
var j = 2*k;
if(j<len && less(arr,j,j+1)) j++;
if(!less(arr,k,j)) break;
exch(arr,k,j);
k = j;
}
}

function less(arr,m,n) {
//可根据不同的数据类型设置比对规则,比如json。这里适用于数字与字符串。
return arr[m]<arr[n];
}

/**
* 交换数组arr中m与n的位置
* @param m
* @param n
*/
function exch(arr,m,n) {
var swap = arr[m];
arr[m] = arr[n];
arr[n] = swap;
}


})(window);

//测试代码
(function () {
//优先队列测试,依次从大到小输出元素
var q = new MaxQueue();
q.insert(3);
q.insert(33);
q.insert(9);
q.insert(21);
while (!q.isEmpty()){
console.log(q.delMax())
}

//堆排序测试代码
var arr = [4,5,6,0,3,5,21,7,9,0,1];
new HeapSort().sort(arr);
console.log(arr);
})();

Java实现

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
package com.algs;

public class Heap {
/**
* 堆排序
* @param pq
*/
public static void sort(Comparable[] pq) {
int n = pq.length;
//构造堆结构
for (int k = n/2; k >= 1; k--)
sink(pq, k, n);
//排序数组
while (n > 1) {
exch(pq, 1, n--);
sink(pq, 1, n);
}
}

//下沉元素
private static void sink(Comparable[] pq, int k, int n) {
while (2*k <= n) {
int j = 2*k;
if (j < n && less(pq, j, j+1)) j++;
if (!less(pq, k, j)) break;
exch(pq, k, j);
k = j;
}
}

//注意这里i和j都减去1
private static boolean less(Comparable[] pq, int i, int j) {
return pq[i-1].compareTo(pq[j-1]) < 0;
}
//注意这里i和j都减去1
private static void exch(Object[] pq, int i, int j) {
Object swap = pq[i-1];
pq[i-1] = pq[j-1];
pq[j-1] = swap;
}

private static void show(Comparable[] a) {
for (int i = 0; i < a.length; i++) {
System.out.println(a[i]);
}
}

public static void main(String[] args) {
String[] a = {"S","O","R","T","E","X","A","M","P","L","E"};
Heap.sort(a);
show(a);
}
}

总结

  1. 不稳定。
  2. 原地排序。
  3. 时间复杂度为NlogN
  4. 空间复杂度为l

GitHub:https://github.com/AlbertKnag/algs-practice

上一篇:排序算法07:三向快速排序
下一篇:排序算法09:总结

赏

谢谢你请我吃糖果

  • 算法

扫一扫,分享到微信

微信分享二维码
排序算法09:总结
排序算法07:三向快速排序
© 2025 YiYing
Hexo Theme Yilia by Litten
  • 所有文章
  • 友链
  • 关于我

tag:

  • 读书笔记
  • sql注入
  • sqlmap
  • nexus
  • HTTP安全
  • restfull
  • 随笔
  • 哲学
  • 缓存
  • HTTP状态码
  • HTTP连接
  • RSA
  • Java
  • JavaScript
  • 安全
  • 排序算法
  • POI
  • 工具类
  • 工作思考
  • Life
  • 读书
  • 前端
  • 团队管理

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录(注意不是yilia根目录)执行以下命令:
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置:

      jsonContent:
        meta: false
        pages: false
        posts:
          title: true
          date: true
          path: true
          text: false
          raw: false
          content: false
          slug: false
          updated: false
          comments: false
          link: false
          permalink: false
          excerpt: false
          categories: false
          tags: true
    

  • 友情链接1
  • 友情链接2
  • 友情链接3
  • 友情链接4
  • 友情链接5
  • 友情链接6
很惭愧

只做了一点微小的工作
谢谢大家