堆排序

堆的定义

堆(二叉堆)可以视为一棵完全的二叉树,完全二叉树的一个“优秀”的性质是,除了最底层之外,每一层都是满的,这使得堆可以利用数组来表示(普通的一般的二叉树通常用链表作为基本容器表示),每一个结点对应数组中的一个元素。
如下图,是一个堆和数组的相互关系

Paste_Image.png

父子节点的运算关系

对于给定的某个结点的下标 i,可以很容易的计算出这个结点的父结点、孩子结点的下标:
Parent(i) = floor(i/2),i 的父节点下标
Left(i) = 2i,i 的左子节点下标
Right(i) = 2
i + 1,i 的右子节点下标

最大堆最小堆

二叉堆一般分为两种:最大堆和最小堆。

最大堆中的最大元素值出现在根结点(堆顶)
堆中每个父节点的元素值都大于等于其孩子结点(如果存在)

最大堆
最小堆中的最小元素值出现在根结点(堆顶)
堆中每个父节点的元素值都小于等于其孩子结点(如果存在)

堆排序

堆排序就是把最大堆堆顶的最大数与末尾的数交换,然后将末尾的数排除大根堆。然后将剩余的堆继续调整为最大堆,再次将堆顶的最大数与末尾的数交换,这个过程持续到剩余数只有一个时结束。在堆中定义以下几种操作:

基本操作

  • Bottom-up reheapify (swim).* If the heap order is violated because a node's key becomes larger than that node's parents key, then we can make progress toward fixing the violation by exchanging the node with its parent. After the exchange, the node is larger than both its children (one is the old parent, and the other is smaller than the old parent because it was a child of that node) but the node may still be larger than its parent. We can fix that violation in the same way, and so forth, moving up the heap until we reach a node with a larger key, or the root.
Paste_Image.png
private void swim(int k) {
   while (k > 1 && less(k/2, k)) {
      exch(k, k/2);
      k = k/2;
   }
}
  • Top-down heapify (sink).* If the heap order is violated because a node's key becomes smaller than one or both of that node's children's keys, then we can make progress toward fixing the violation by exchanging the node with the larger of its two children. This switch may cause a violation at the child; we fix that violation in the same way, and so forth, moving down the heap until we reach a node with both children smaller, or the bottom.
Paste_Image.png
private void sink(int k) {
   while (2*k <= N) {
      int j = 2*k;
      if (j < N && less(j, j+1)) j++;
      if (!less(k, j)) break;
      exch(k, j);
      k = j;
   }
}
  • Insert. We add the new item at the end of the array, increment the size of the heap, and then swim up through the heap with that item to restore the heap condition.
  • Remove the maximum. We take the largest item off the top, put the item from the end of the heap at the top, decrement the size of the heap, and then sink down through the heap with that item to restore the heap condition.
    Paste_Image.png

实现

分为两步,先建堆再进行下沉堆排序。
建堆过程是从末尾节点的孩子开始进行下沉(sink)操作,依次执行直到头结点,此时建成大根堆。
堆排序则是将头结点和尾节点交换,将尾节点从堆中删除,然后对头结点进行下沉操作。

Paste_Image.png
public void heapSort(int[] array, int n) {
    //建堆过程
    for(int i=(array.length-1)/2;i>=0;i--){
        sink(array,i,array.length-1);
    }   
    for(int i=n-1;i>0;i--){
        swap(array,0,i);
        sink(array,0,i-1);
    }   
}
    
private void sink(int[] array,int lo,int hi){
    while(lo*2+1<=hi){
        int left=lo*2+1;
        if(left<hi&&array[left]<array[left+1]) left++;
        if(array[lo]>=array[left])break;
        swap(array,left,lo);
        lo=left;
    }
}
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 201,681评论 5 474
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 84,710评论 2 377
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 148,623评论 0 334
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 54,202评论 1 272
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 63,232评论 5 363
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,368评论 1 281
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 37,795评论 3 393
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,461评论 0 256
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 40,647评论 1 295
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,476评论 2 317
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,525评论 1 329
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,226评论 3 318
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 38,785评论 3 303
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,857评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,090评论 1 258
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 42,647评论 2 348
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,215评论 2 341

推荐阅读更多精彩内容

  • 关于最大堆 什么是最大堆和最小堆?最大(小)堆是指在树中,存在一个结点而且该结点有儿子结点,该结点的data域值都...
    凌云壮志几多愁阅读 87,827评论 33 71
  • 堆排序的时间复杂度与归并排序相同为O(nlg n),空间复杂度与插入排序相同为O(1)。堆这种数据结构还用于优先队...
    Nautilus1阅读 907评论 1 0
  • 堆排序与快速排序[https://www.jianshu.com/p/2cc8fc1c878f],归并排序[htt...
    爱情小傻蛋阅读 1,131评论 1 7
  • 今天,有机会和朋友一起去了古中山国遗址博物馆。 一路上朋友的车很快,一路狂飙的爽。一段高速,两边秋草枯黄,朔风野大...
    心如美玉阅读 205评论 2 1
  • 黑夜,只不过是上帝用黑色的纱遮住了天空的眼眸,忘了揭开罢了。 夜空一片漆黑,就像人的黑色的眼眸一般深沉...
    子巷阅读 348评论 0 2