算法导论第六章堆排序(一)

现在来看, 堆的含义大概有两种,一种是数据结构,一种是在一些语言中所定义的“垃圾回收机制”,如Java,在书本上的开篇强调了这两者,并强调若非特殊说明,皆把堆看做是一种数据结构。

(二叉)堆的定义:

1)它是一个数组,可以被看成是一棵近似的完全二叉树,树上的每一个节点看做是数组中的每一个元素。

2)堆分为最大堆和最小堆,最大堆中每一棵子树的父节点的值大于孩子节点,最小堆则相反。

3)表示堆的数组A包括两个属性:A.length和A.heap_size。前者是数组元素的个数,后者是堆元素的个数,heap_size <= length。(怎么理解这里,想象一棵树的节点在减少,但其表示的数组的个数还是不变的)。

4)二叉堆是最常用的,除此之外,还有多叉堆,如习题6-2的d-叉堆。

5)已知一个节点的坐标,容易得到其父节点和孩子节点的坐标:PARENT(i) = i/2; LEFT(i) = 2*i; RIGHT(i)=2*i+1。

由于二叉堆可以看做是一棵完全二叉树,所以树的一些定理,结论可以应用到堆上,如高度为h的堆中元素个数最多为:2^h,最少为:2^(h+1) - 1; 含n个元素的堆高度为:lgn。

堆排序:

为了实现堆排序,需要有这样的几个过程:

1)Build_Max_Heap():建立最大堆,将无序的输入数组构造出一个最大堆;

2)Max_Heapify():维护一个最大堆,即保证满足最大堆的性质;

3)Heap_Sort():堆排序。

以上函数的思路也是比较简单,在此就不做过多记录,即便记录,也是照着书本上的流程来一遍。

首先,Max_Heapify()是一个很关键的函数,它要保证堆中元素在以后的操作过程中,不管怎么变,都要保证满足最大堆的性质,即父节点的值永远大于孩子节点,知道了这一点,就不难写出代码:

函数原型:Max_Heapify( int A[], /* int heap_size, */ int index )

 1 void MaxHeapify_Recur(int arr[], int heap_size, int index)
 2 {
 3     if (index <=0 && index >= heap_size)
 4         return;
 5 
 6     int left = LEFT(index);
 7     int right = RIGHT(index);
 8     int largest;
 9 
10     if (left < heap_size && arr[left] > arr[index])
11         largest = left;
12     else 
13         largest = index;
14 
15     if (right < heap_size && arr[right] > arr[largest])
16         largest = right;
17 
18     if (largest != index) {
19         Swap(arr[index], arr[largest]);
20         MaxHeapify_Recur(arr, heap_size, largest);
21     }
22 }

上面实现的是一个递归的版本,也是书本上的版本,同时习题6.2-5要求实现非递归的版本,其实改动很小,只需加入一个标识符即可,实现如下:

 1 void MaxHeapify(int arr[], int heap_size, int index)
 2 {
 3     if (index < 0 && index >= heap_size)
 4         return;
 5     
 6     bool isHeapify = true; //标识最大堆是否处理完
 7     while (isHeapify && index < heap_size) {
 8         int left = LEFT(index);
 9         int right = RIGHT(index);
10         int largest;
11 
12         if (left < heap_size && arr[left] > arr[index]) 
13             largest = left;
14         else 
15             largest = index;
16 
17         if (right < heap_size && arr[right] > arr[largest])
18             largest = right;
19 
20         if (largest != index) {
21             Swap(arr[index], arr[largest]);
22             index = largest;
23         }
24         else
25             isHeapify = false;
26     }
27 }

其次,Build_Max_Heap()的实现需要知道下面一条定理( 习题6.1-7 ) :

当用数组表示存储n个元素的堆时,叶节点下标分别是n/2+1, n/2+2, ..., n (结合树高度的性质,很好证明).

知道了这个定理,为了建立最大堆,我们就可以从第一个非叶子节点开始往后遍历,直到根节点,调用Max_Heapify()来得到一个最大堆,实现如下:

函数原型:Build_Max_Heap( int A[], /* int heap_size, */ )

1 void BuildMaxHeap(int arr[], int heap_size)
2 {
3     if (heap_size == 0)
4         return;
5     
6     for (int i = (heap_size-1)/2; i >= 0; i--)
7         MaxHeapify(arr, heap_size, i);
8 }

至此,排序思路也就出来了:先建立最大堆,得到最大元素,然后将最大元素放在数组末尾,然后调用Max_Heapify()维护最大堆,依次下去,就得到排序的数组,实现如下:

函数原型:Heap_Sort( int A[], /* int heap_size, */ )

 1 void HeapSort(int arr[], int length)
 2 {
 3     if (length == 0)
 4         return;
 5 
 6     int heap_size = length;
 7     BuildMaxHeap(arr, heap_size);
 8     for (int i = length-1; i >= 1; i --) {
 9         Swap(arr[0], arr[i]);
10         heap_size --;
11         MaxHeapify(arr, heap_size, 0);
12     }
13 }

堆排序的时间复杂度:

Max_Heapify()可以看到是在不断遍历树,最坏情况下是从根节点开始,则n个节点的树高为lgn,所以其时间复杂度为O(lgn)。

Build_Max_Heap()经过严格推导,可得时间复杂度为线性的,为O(n)。

所以,Heap_Sort()就为O(nlgn)。

同样的思路可以实现最小堆,下面贴出最大堆完整实现的代码:

  1 #include <iostream>
  2 
  3 using namespace std;
  4 
  5 
  6 //#include "HeapSort.h"
  7 
  8 #define PARENT(x) ((x-1)/2)    //求 x 父节点的下标
  9 #define LEFT(x) ((x)*2+1)    //求 x 左孩子的下标
 10 #define RIGHT(x) ((x)*2+2)    //求 x 右孩子的下标
 11 
 12 void MaxHeapify(int arr[], int heap_size, int index);        //维护最大堆的性质
 13 void MaxHeapify_Recur(int arr[], int heap_size, int index); //递归
 14 void BuildMaxHeap(int arr[], int heap_size);                    //从一个无序的数组中构造一个最大堆
 15 void HeapSort(int arr[], int length);                            //堆排序
 16 void Swap(int &a, int &b);
 17 
 18 void MaxHeapify(int arr[], int heap_size, int index)
 19 {
 20     if (index < 0 && index >= heap_size)
 21         return;
 22     
 23     bool isHeapify = true; //标识最大堆是否处理完
 24     while (isHeapify && index < heap_size) {
 25         int left = LEFT(index);
 26         int right = RIGHT(index);
 27         int largest;
 28 
 29         if (left < heap_size && arr[left] > arr[index]) 
 30             largest = left;
 31         else 
 32             largest = index;
 33 
 34         if (right < heap_size && arr[right] > arr[largest])
 35             largest = right;
 36 
 37         if (largest != index) {
 38             Swap(arr[index], arr[largest]);
 39             index = largest;
 40         }
 41         else
 42             isHeapify = false;
 43     }
 44 }
 45 
 46 void MaxHeapify_Recur(int arr[], int heap_size, int index)
 47 {
 48     if (index <=0 && index >= heap_size)
 49         return;
 50 
 51     int left = LEFT(index);
 52     int right = RIGHT(index);
 53     int largest;
 54 
 55     if (left < heap_size && arr[left] > arr[index])
 56         largest = left;
 57     else 
 58         largest = index;
 59 
 60     if (right < heap_size && arr[right] > arr[largest])
 61         largest = right;
 62 
 63     if (largest != index) {
 64         Swap(arr[index], arr[largest]);
 65         MaxHeapify_Recur(arr, heap_size, largest);
 66     }
 67 }
 68 
 69 void BuildMaxHeap(int arr[], int heap_size)
 70 {
 71     if (heap_size == 0)
 72         return;
 73     
 74     for (int i = (heap_size-1)/2; i >= 0; i--)
 75         MaxHeapify(arr, heap_size, i);
 76 }
 77 
 78 void HeapSort(int arr[], int length)
 79 {
 80     if (length == 0)
 81         return;
 82 
 83     int heap_size = length;
 84     BuildMaxHeap(arr, heap_size);
 85     for (int i = length-1; i >= 1; i --) {
 86         Swap(arr[0], arr[i]);
 87         heap_size --;
 88         MaxHeapify(arr, heap_size, 0);
 89     }
 90 }
 91 
 92 void Swap(int &a, int &b)
 93 {
 94     int temp = a;
 95     a = b;
 96     b = temp;
 97 }
 98 
 99 // int main()
100 // {
101 //     int arr[10] = {10,14,16,8,7,9,3,2,4,1};
102 //     HeapSort(arr, 10);
103 //     for (int i = 0; i < 10; i ++)
104 //         cout << arr[i] << " ";
105 //     return 0;
106 // }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏猿人谷

Single Number and Single Number II

[1] Given an array of integers, every element appears twice except for one. Find...

2165
来自专栏desperate633

LeetCode Delete Node in a Linked ListQuestion题目分析代码

给定一个单链表中的一个等待被删除的节点(非表头或表尾)。请在在O(1)时间复杂度删除该链表节点。

813
来自专栏恰童鞋骚年

数据结构基础温故-1.线性表(上)

开篇:线性表是最简单也是在编程当中使用最多的一种数据结构。例如,英文字母表(A,B,C,D...,Z)就是一个线性表,表中的每一个英文字母都是一个数据元素;又如...

661
来自专栏数据结构与算法

洛谷P3380 【模板】二逼平衡树(树套树)

您需要写一种数据结构(可参考题目标题),来维护一个有序数列,其中需要提供以下操作:

2863
来自专栏拭心的安卓进阶之路

Java 集合源码解析(2):ListIterator

今天心情和股票一样红,还是学学 ListIterator 吧! ListIterator ? 根据官方文档介绍, ListIterator 有以下功能: 允许...

2169
来自专栏Java编程

Java HashMap那点事

HashMap 和 HashSet 是 Java Collection Framework 的两个重要成员,其中 HashMap 是 Map 接口的常用实现类,...

4250
来自专栏Java进阶架构师

对HashMap的思考及手写实现

HashMap是Java中常用的集合,而且HashMap的一些思想,对于我们平时解决业务上的一些问题,在思路上有帮助,基于此,本篇博客将分析HashMap底层设...

982
来自专栏coolblog.xyz技术专栏

LinkedHashMap 源码详细分析(JDK1.8)

LinkedHashMap 继承自 HashMap,在 HashMap 基础上,通过维护一条双向链表,解决了 HashMap 不能随时保持遍历顺序和插入顺序一致...

49610
来自专栏架构说

题目:将链表的奇数位和偶数位调换组成新的链表

题目:将链表的奇数位和偶数位调换组成新的链表 原题链接: http://oj.leetcode.com/problems/swap-nodes-in-pairs...

5449
来自专栏对角另一面

lodash源码分析之compact中的遍历

本文为读 lodash 源码的第三篇,后续文章会更新到这个仓库中,欢迎 star:pocket-lodash

2186

扫码关注云+社区

领取腾讯云代金券