首页 > 代码库 > Chapter 6 堆排序
Chapter 6 堆排序
-------------------注明----------------
以下内容来自于《算法导论》 lz新手，存在各种错误以及各种不合理的地方望大家指出
堆排序时间复杂度为O(nlgn),并且就有空间原址性：任何时候都只需常数个额外的元素空间存储临时数据
6.1 堆
堆是一个数组，但可以被看做近似的完全二叉树，树上的每个结点对应数组中的一个元素。除最底层外，该树是完全充满的！
实例(原书上的图)：
可分为最大堆和最小堆，最大堆性质：A[parent(i)]≥A[i]
---------练习--------
6.1-1 在高度为h的堆中，元素个数最多和最少分别是多少？(注：先说明高度这个概念,如图(a)高度就为3)
max=2h+1-1 min=2h
6.1-2 证明含n个元素的堆的高度为小于等于lgn的整数
对于具有k层的完全二叉树有 1+2+22+...2k=(1-2k+1)/(1-2)=2k+1-1
从而易得含有n个元素的堆落在哪一层，即2k-1<n<2k+1-1
结合k要取整数，从而得证
----------------------
6.2 使堆“恢复”最大堆的性质(Maintaining the heap property)
为解决在后续操作中出现第i位置的子结点不满足最大堆性质(但i的各子结点满足最大堆性质)，建立"恢复"i为根时最大堆性质的函数(注：以下维护只能保证i和他的儿子满足最大堆性质，而不能保证他的儿子和他的儿子的儿子满足最大堆性质)
static void MaxHeapify(List<int> array,int i,int length) //此处加个length是为了堆排序时取出最大下标 { int largest = i; int left = 2 * i + 1, right = 2 * i + 2; if (left < length && array[left] > array[i]) //找出i,2i+1,2i+2中最大那个值的下标 largest = left; if (right < length && array[right] > array[largest]) largest = right; if(largest!=i) { int temp = array[i]; //将最大值放入i中 array[i] = array[largest]; array[largest] = temp; MaxHeapify(array, largest,length); //将被改动那个下标再次递归进行维护 } }
------练习------
6.2-2 维护相应最小堆的Code：
static void MinHeapify(List<int> array, int i) { int min = i, length = array.Count; int left = 2 * i + 1, right = 2 * i + 2; if (left < length && array[left] < array[i]) //找出i,2i+1,2i+2中最小那个值的下标 min = left; if (right < length && array[right] < array[min]) min = right; if (min != i) { int temp = array[i]; //将最小值放入i中 array[i] = array[min]; array[min] = temp; MinHeapify(array, min); //将被改动那个下标再次递归进行维护 } }
6.2-5 使用循环控制结构取代递归，重写MaxHeapify，Code如下：
static void MaxHeapify2(List<int> array,int i) { int largest = i, left = 0, right = 0; while(true) //用来取代递归 { left = 2 * i + 1; right = 2 * i + 2; if (left < array.Count && array[left] > array[i]) largest = left; if (right < array.Count && array[right] > array[largest]) largest = right; if (i != largest) { int temp = array[i]; array[i] = array[largest]; array[largest] = temp; i = largest; } else break; } }
-----------------
6.3 建堆(Building a heap)
为了将整个"杂乱无章"的数组转换为具有最大堆的性质，我们需要对每个含有子结点的结点进行"MaxHeapify"，并且需要从底往上(即从(n-1)/2 to 0)进行
static void BuildMaxHeap(List<int> array) { for (int i = (array.Count - 2) / 2; i >= 0; i--) //此处i从(n-2)/2开始,因为没有子节点的节点无需进行"维护" MaxHeapify(array, i,array.Count); }
6.4 堆排序算法
根据最大堆的特点，根结点的值最大，因此可以采取每次将根结点取出(用数组末尾的数顶上)，取出并替换后的堆除根结点外均满足最大堆性质，因此满足Maxheapify的要求！---最大堆化一次又恢复到最大堆性质，从而不断进行便ok！
static void HeapSort(List<int> array) { BuildMaxHeap(array); for(int i=array.Count-1;i>0;i--) //每次将堆得根与最大下标的值互换,并将最大下标"剔除" { int temp = array[i]; array[i] = array[0]; array[0] = temp; MaxHeapify(array, 0,i); } }
6.5 优先队列
应用堆的优先序列其实本质上只是在最大或最小堆的形式上，加入一些功能，如：
- Insert(S,x)：把元素x插入集合S中，这一操作等价于 S=S∪{x}
- Maximum(S)：返回S中具有最大键字的元素
- ExtractMax(S)：去掉并返回S中的具有最大键字的元素
- IncreaseKey(S,x,k)：将元素x的关键字值增加到k，这里假设k的值不小于x的关键字值
Maximum操作(其中的array已经是经过最大堆处理)：
static int HeapMaximum(List<int> array) { return array[0]; }
ExtractMax操作(此操作过后，array的元素少一个)：
static int HeapExtractMax(List<int> array) { if (array.Count < 1) return -1; int max = array[0]; array[0] = array[array.Count - 1]; array.RemoveAt(array.Count - 1); //移除array.count-1这个下标 MaxHeapify(array, 0,array.Count); //维护堆,本身被破坏的也只array[0] return max; }
IncreaseKey：
static void HeapIncreaseKey(List<int> array,int i,int key) { if (key < array[i]) //这种"抛出异常写法不规范,偷懒而已" { Console.WriteLine("出错,key 必须大于array[i]!"); return; } array[i] = key; while(i>0&&array[(i-1)/2]<array[i]) //此while为了维护最大堆的性质 { int temp = array[i]; array[i] = array[(i - 1) / 2]; array[(i - 1) / 2] = temp; i = (i - 1) / 2; } }
Insert：
static void MaxHeapInsert(List<int> array,int key) { array.Add(key); HeapIncreaseKey(array, array.Count - 1, key); }
--------练习--------
6.5-6 利用插入排序内循环部分的思想，只用一次赋值来完成IncreaseKey中的 array[i]与array[parent[i]]互换(原本需要三次赋值,即引入了temp)
static void HeapIncreaseKey(List<int> array,int i,int key) { if (key < array[i]) //这种"抛出异常写法不规范,偷懒而已" { Console.WriteLine("出错,key 必须大于array[i]!"); return; } array[i] = key; while(i>0&&array[(i-1)/2]<key) //此while为了维护最大堆的性质 { array[i] = array[(i - 1) / 2]; i = (i - 1) / 2; } array[i] = key; }
6.5-8 HeapDelete(S,i)：将结点i从堆S中删除：
static void HeapDelete(List<int> array, int i) { array[i] = array[array.Count - 1]; //将最后一个值取代要删除位置的值 array.RemoveAt(array.Count - 1); MaxHeapify(array, i, array.Count); //i位置值变化了,因此对此处进行"维护" }
6.5-9 将k个有序链表合并为一个有序链表，并且时间复杂度为O(nlgk)，此处n是所有输入链表包含的总的元素个数
思路： 1. 从k个链表中取出每个链表的第一个元素，组成一个大小为k的数组arr，然后将数组arr转换为最小堆，那么arr[0]就为最小元素了
2.取出arr[0]，将其放到新的链表中，然后将arr[0]元素在原链表中的下一个元素补到arr[0]处，即arr[0].next，如果 arr[0].next为空，即它所在的链表 的元素已经取完了，那么将堆的最后一个元素补到arr[0]处，堆的大小自动减一，循环n-k次即可。
(注：以上思路参考于http://www.cnblogs.com/shuaiwhu/archive/2011/03/20/2065077.html)
Code分为以下几个模块：
①最小堆维护模块(输入数组为LinkedListNode<int>类型)
static void MinHeapify(List<LinkedListNode<int>> array, int i) { int min = i, length = array.Count; int left = 2 * i + 1, right = 2 * i + 2; if (left < length && array[left].Value< array[i].Value) //找出i,2i+1,2i+2中最小那个值的下标 min = left; if (right < length && array[right].Value< array[min].Value) min = right; if (min != i) { LinkedListNode<int> temp = array[i]; //将最小值放入i中 array[i] = array[min]; array[min] = temp; MinHeapify(array, min); //将被改动那个下标再次递归进行维护 } }
②最小堆建堆模块
static void BuildMinHeap(List<LinkedListNode<int>> array) { for (int i = (array.Count - 2) / 2; i >= 0; i--) //此处i从(n-2)/2开始,因为没有子节点的节点无需进行"维护" MinHeapify(array, i); }
③将k个链表结合成一个链表
static LinkedList<int> CombineLink(List<LinkedList<int>> link) { LinkedList<int> result=new LinkedList<int>(); List<LinkedListNode<int>> array = new List<LinkedListNode<int>>(); foreach (LinkedList<int> l in link) //将每个链表的第一个Node取出,存入数组array array.Add(l.First); BuildMinHeap(array); //建立最小堆 while (array.Count!=0) { MinHeapify(array,0); //由于每次array[0]均变化,所以需要进行维护 result.AddLast(array[0].Value); if (array[0].Next != null) //元素未取完时,将原链表中的下一个元素补到arr[0]处 array[0] = array[0].Next; else //一个链表元素取完情况 { array[0] = array[array.Count - 1]; array.RemoveAt(array.Count - 1); } } return result; }
一次测试结果：
------------------
Chapter 6 堆排序