中断了一年,终于有时间再开始了。希望还有人记得,继续支持。Blog地址如下:
《算法导论的Java实现》 7 堆排序
7 堆排序7.1 堆堆的概念不想多介绍,书上都有。这里只提几个基本概念,以说明后面的伪代码。
堆可以看出一颗完全二叉树,除了最后一层,树的每一层都是填满的,最后一层,也是从左至右填。
在堆排序里面,堆就用数组表示,不需要其他的数据结构(因为是完全二叉树),观察后面伪代码,可以看出,对于完全二叉树,用3个函数(用C来实现的话是3个宏(macro)),可以确定任何一个节点的父子节点。
想强调的是,这里没有一个叫“堆”的数据结构,它只是个数组,堆(完全二叉树)存在于我们的脑子了,我们用本篇后面介绍的很多方法来操作这个很普通的数组,所有的方法的集合,就赋予了这个普通的数组以“堆”的属性。
类似的,如果有个双向链表(数组也可以),我们赋予它先进先出的存取方法集合,那么它就是个“队列”;如果我们赋予它先进后出的存取方法集合,那么它就是个“栈”。队列和栈本身没有与众不同的实体,它们只是普通的链表(或者数组),队列和栈是存在于我们脑子中的。所谓“运用之妙,存乎一心”(《宋史·岳飞传》)就在于此。
伪代码:
PARENT(i)
   return ┕i/2┙LEFT(i)
   return 2iRIGHT(i)
   return 2i + 1Java代码:    public static int parent(int i) {
        return (i - 1) >> 1;
    }    public static int left(int i) {
        return ((i + 1) << 1) - 1;
    }    public static int right(int i) {
        return (i + 1) << 1;
    }
    public static void main(String[] args) {        for (int i = 0; i < 10; i++) {
            System.out.print(parent(i) + " ");
            System.out.print(left(i) + " ");
            System.out.println(right(i) + " ");
        }
    }
输出:
-1 1 2 
0 3 4 
0 5 6 
1 7 8 
1 9 10 
2 11 12 
2 13 14 
3 15 16 
3 17 18 
4 19 20 上面输出的是对于每个节点(0到9)的父节点,左子节点,右子节点的数组下标。
根节点0的父节点是-1(伪代码里面是0)。
要说明的是:伪代码里面的乘2除2运算,我在Java里面都用了位移操作。这更符合堆排序的本意。在C和汇编里,位移运算比乘除要快得多。位移运算比加减更快,可能只占一个CPU时钟,乘除要占20多个以上,差了一个数量级。效率而言,那是差不起的。7.2 保持堆的性质伪代码:
MAX-HEAPIFY(A, i)
 1 l ← LEFT(i)
 2 r ← RIGHT(i)
 3 if l ≤ heap-size[A] and A[l] > A[i]
 4    then largest ← l
 5    else largest ← i
 6 if r ≤ heap-size[A] and A[r] > A[largest]
 7    then largest ← r
 8 if largest ≠ i
 9    then exchange A[i] ←→ A[largest]
10         MAX-HEAPIFY(A, largest)Java代码:    public static <T> void heapify(T[] a, int i, Comparator<? super T> c) {        int l = left(i);
        int r = right(i);        int next = i;
        if (l < a.length && c.compare(a[l], a[i]) > 0)
            next = l;
        if (r < a.length && c.compare(a[r], a[next]) > 0)
            next = r;
        if (i == next)
            return;
        swap(a, i, next);
        heapify(a, next, c);    }    private static void swap(Object[] arr, int i, int j) {        Object tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }    /**
     * @param args
     */
    public static void main(String[] args) {        //heapify test
        Integer[] temp = new Integer[] {
            5, 2, 4, 6, 1, 3, 2, 6
        };        heapify(temp, 1, new Comparator<Integer>() {            @Override
            public int compare(Integer o1, Integer o2) {                return o1 - o2;
            }        });        for (int i : temp) {
            System.out.print(i + " ");
        }
        System.out.println();
    }输出:
5 6 4 6 1 3 2 2 这里如果不说明一下,可能有点理解困难,因为我的文章里面没有图,二叉树的图像必须存在于自己的脑子里。如果参考了《算法导论》里,这个章节的堆的二叉树图像的话,将容易理解得多。
我这个测试代码里,输入的是:5, 2, 4, 6, 1, 3, 2, 6
它的图像如下:                5
         2            4
      6     1      3     2
    6如果,你还没有理解堆是怎么一回事儿,那就就把上面这个二叉树,从上到下,从左到右,遍历一遍,别去管树的父子关系。从上到下,从左到右,遍历的结果,就是原来的输入:5, 2, 4, 6, 1, 3, 2, 6。也就是我前面说过的,数组还是那个数组,但是“存乎一心”的去想象,在脑子里,把数组的元素一个一个抽出,放到二叉树里面,第一行放一个(根),第二行放2个,第三行放4个,……,第n行放2^(n-1)个,放完为止,最下面一行,右面部分可以为空,别的地方都应该是满的,这就是堆(完全二叉树)。
然后,测试时,调用heapify函数,参数是1,也就是说对第二个元素进行重排,也就是上面二叉树图像里面第二行最左面的元素“2”进行重排。heapify里面,会把“2”和它的左右节点“6”和“1”进行比较,得出左节点“6”最大(比自己和右节点大)。就把自己(“2”)和左节点“6”进行交换,然后递归左节点(第4个元素,下标为3)。交换以后,原来的左节点(第4个元素,下标为3)的值是本身“2”,再一次(递归)判断自己和左右节点的关系,由于没有右节点,就只需要和左节点,最下层那个孤零零的“6”进行比较,然后交换。最后得出的图像如下:                5
         6            4
      6     1      3     2
    2 上面的图像还原成数组,也就是我的程序的输出结果:5 6 4 6 1 3 2 2 堆排序里面,上面这个函数是最核心部分,它非常的漂亮(自我感觉Java程序比伪代码更加漂亮,呵呵),所以整个堆排序也是非常漂亮的一种排序。
7.3 建堆伪代码:
BUILD-MAX-HEAP(A)
1  heap-size[A] ← length[A]
2  for i ← ┕length[A]/2┙ downto 1
3       do MAX-HEAPIFY(A, i)Java代码:    public static <T> void buildHeap(T[] a, Comparator<? super T> c) {        for (int i = (a.length + 1) / 2 - 1; i >= 0; i--) {
            heapify(a, i, c);
        }    }    /**
     * @param args
     */
    public static void main(String[] args) {
        //buildHeap test
        Integer[] temp = new Integer[] {
            5, 2, 4, 6, 1, 3, 2, 6
        };        buildHeap(temp, new Comparator<Integer>() {            @Override
            public int compare(Integer o1, Integer o2) {                return o1 - o2;
            }
        });        for (int i : temp) {
            System.out.print(i + " ");
        }
        System.out.println();
    }
输出:
6 6 4 5 1 3 2 2 有了前面的基础,把这个输出想象成一个二叉树,应该不太困难了:                6
         6            4
      5     1      3     2
    2 上面就是一个建好的堆,它满足每个节点都比自己的子节点要大。
稍微要说明一下的是:for i ← ┕length[A]/2┙ downto 1
为什么从┕length[A]/2┙开始?因为我们不用重排叶子节点。
我的测试数组中,一共8个元素,也就是只要从第4个元素开始循环就可以了。大家可以验证一下,第4个元素也就是第3行的第一个元素,最后的结果是“5”的那个节点,它是最后一个有儿子的节点,从它往后,都是叶子节点了。为什么只要除以二再向下取整,为什么会如此简洁?一切的起因就是:它是一颗二叉树,每一层的个数是2^(n-1),全满的时候,总数是2^n个。
7.4 堆排序算法伪代码:
HEAPSORT(A)
1 BUILD-MAX-HEAP(A)
2 for i ← length[A] downto 2
3    do exchange A[1] ←→ A[i]
4       heap-size[A] ← heap-size[A] - 1
5       MAX-HEAPIFY(A, 1)对已经建立好的堆,运行上面的伪代码后,就可以得到,排好顺序的数组了。
但是,直接看上面的伪代码,并不是很容易理解,那就要仔细看一下《算法导论》的原文了。
我这里简单介绍一下思路:第一次建立好堆之后,第一个元素(根)就是我们要的排好序的第一个元素;把这个元素和最后一个元素进行交换(也就是抽出),然后调用HEAPIFY函数,进行重组堆。
这里要注意:重组堆重组所有的数组元素,而是重组从第一元素开始到没有被抽出的元素为止。这里要用到伪代码的heap-size[A],它看上去像一个函数,但其实它只是个变量。之所以,我前面的Java实现都没有管这个变量,那是因为一直没有用到,建堆时,是把整个数组都当成一个堆的,不需把后面若干元素排除在外。
现在,我们需要这个heap-size[A]变量了,它为我们指出,当前堆的最后一个元素,而这个元素之后的都是已经被抽出,已经排序好的元素。
下面的Java实现里,会重载(overload)heapify这个函数,没有搞清什么叫重载(overload),什么叫重写(override)和多态(polymorphism)的,要自己回家好好看书。Java代码:import java.util.Comparator;public class HeapSort {    public static int parent(int i) {        return (i - 1) >> 1;
    }    public static int left(int i) {        return ((i + 1) << 1) - 1;
    }    public static int right(int i) {        return (i + 1) << 1;
    }    private static void swap(Object[] arr, int i, int j) {        Object tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }    public static <T> void heapify(T[] a, int i, Comparator<? super T> c, int size) {        int l = left(i);
        int r = right(i);        int next = i;
        if (l < size && c.compare(a[l], a[i]) > 0)
            next = l;
        if (r < size && c.compare(a[r], a[next]) > 0)
            next = r;
        if (i == next)
            return;
        swap(a, i, next);
        heapify(a, next, c, size);    }    public static <T> void heapify(T[] a, int i, Comparator<? super T> c) {        heapify(a, i, c, a.length);
    }    public static <T> void buildHeap(T[] a, Comparator<? super T> c) {        for (int i = (a.length + 1) / 2 - 1; i >= 0; i--) {
            heapify(a, i, c);
        }    }    public static <T> void heapSort(T[] a, Comparator<? super T> c) {        buildHeap(a, c);
        for (int i = a.length - 1; i > 1; i--) {
            swap(a, 0, i);
            heapify(a, 0, c, i - 1);
        }
    }    public static void main(String[] args) {        //heapSort test
        Integer[] temp = new Integer[] {
            5, 2, 4, 6, 1, 3, 2, 6
        };        heapSort(temp, new Comparator<Integer>() {            @Override
            public int compare(Integer o1, Integer o2) {                return o1 - o2;
            }
        });        for (int i : temp) {
            System.out.print(i + " ");
        }
        System.out.println();    }}输出:
1 2 2 3 4 5 6 6 前面,我给出的都是和伪代码相对应的Java代码片段。而直到这里,我把所有的代码都给出了,因为我们的堆排序已经完成了。coding后感
这次的感想不多,因为很多要说的,在上面各段伪代码说明时都说了。
之所以针对每段伪代码都做了说明,是因为堆排序不如别的排序(插入,选择,冒泡)那么直观,需要动脑筋想象二叉树。
数组下标的差异,在堆排序里,没有造成太大的困扰,甚至于,因为Java数组下标从零开始,反而使Java的代码更加的漂亮。
堆排序的程序量其实不多,但是heapify,buildHeap,heapSort这3个函数各司其职,配合的丝丝入扣。7.5 优先级队列伪代码:HEAP-EXTRACT-MAX(A)
1 if heap-size[A] < 1
2   then error "heap underflow"
3 max ← A[1]
4 A[1] ← A[heap-size[A]]
5 heap-size[A] ← heap-size[A] - 1
6 MAX-HEAPIFY(A, 1)
7 return max伪代码:HEAP-INCREASE-KEY(A, i, key)
1 if key < A[i]
2   then error "new key is smaller than current key"
3 A[i] ← key
4 while i > 1 and A[PARENT(i)] < A[i]
5     do exchange A[i] ↔ A[PARENT(i)]
6         i ← PARENT(i)MAX-HEAP-INSERT(A, key)
1 heap-size[A] ← heap-size[A] + 1
2 A[heap-size[A]] ← -∞
3 HEAP-INCREASE-KEY(A, heap-size[A], key)code后感
上面的伪代码,我写了一点点就放弃了,所以没有Java代码提供给大家。因为实在没有太大的意思。
优先级队列是一个堆的应用,堆排序完成后,原来的代码上增加堆的追加和删除操作后,可以形成一个实用的优先级队列。大学三年级时,学操作系统时,我们都做过作业,自己做个小型的分时系统,进程调度管理,我本来准备参考windows的,因为linux的程序是公开,同学大多抄袭linux代码,而我想干点有难度的,就去反编译windows。后来发现,就内核而言,windows95根本就不是个多进程系统。到后来,我才知道,原来当然微软正从DOS的单进程往windows的多进程进发,而其主程序员实在太蹩脚,根本不懂多进程,所以windows95的多进程完全是个假的。当时,如果我知道有这个优先级队列的话,就不会去跟踪windows的内核了,也可以节约很多时间。
说到微软的蹩脚程序员,不得不说我当年学VC的经历。我学的时候VC还是4.0,后来做毕业设计的时候是6.0。和现在学Java一样,我花了很多时间去研究MFC的源代码,后来发现VC4.0的CD里面有个目录,里面的C/C++代码,非常的优美,让人赏心悦目;而其他的地方,写得还不如俺的一些同学。后来有人告诉我,我看的实际上是HP的代码,他们帮微软在做事儿。后来的VC6.0已经把HP的代码买下来,融入自己的了。不过就算如此,我还是发现,VC6.0的伪随机函数是错的。我曾直接联系他们的总部,报告random这个bug。98年的时候,我虽然已经开始用Internet好几年了,但是没有email,他们的态度倒是挺好,直接从西雅图邮国际信件给俺,说知道这个bug了,会处理的。不过后来,俺毕业后,开始的工作是汇编,然后是Java,再也没有碰过微软的东西,不知道他们bug是不是还是那么多,内部的source还是那么烂。

解决方案 »

  1.   

    沙发这种东西还是很不错的,特别是对我这种算法超级菜鸟来说,很有意义,希望楼主坚持我老是觉得,很多教材(貌似是很权威的教材),讲的东西模模糊糊,关键点根本不讲比如《某某数据结构》图的介绍居然邻接表和邻接矩阵只说,这个是邻接矩阵,这个是邻接表,其他的什么都没讲居然后面就讲什么图的遍历之类的东西。唉,舍本逐末不说,看得我是云里雾里。直到看了《Java数据结构》,才发现,邻接表和邻接矩阵是干什么用的才知道图的遍历为什么需要这东西。而且第二版的《Java数据结构》中,介绍了邻接表和邻接矩阵的概念之后根本没讲遍历的实现,只是启发一下读者,让自己去写。我还是比较喜欢这类的教材的。之前织了个围脖,说了一下上面的情况,居然发现我国经典教材《XX数据结构》粉丝甚众被人喷的屁滚尿流。再也不敢乱说话了。
      

  2.   

    思路的话,《算法导论》里面讲得非常清楚,俺就不越权了。
    俺的本意是用Java实现一遍《算法导论》里面所有的伪代码。
    然后再把实现途中碰到的问题和心得介绍给大家。
      

  3.   

    谢谢楼主的代码和描述,这样有助于我更快的理解算法。
    有些地方有问题   public static <T> void heapSort(T[] a, Comparator<? super T> c) {        buildHeap(a, c);
            for (int i = a.length - 1; i > 1; i--) {
                swap(a, 0, i);
                heapify(a, 0, c, i - 1);
            }
        }
    红色部分要改成i>0
    瑕不掩瑜,支持楼主写更多的算法BLOG
      

  4.   


    首先,谢谢你仔细看,仔细调试。
    但是,你指出的地方,我并没错。呵呵。
    如果照你的来改,程序输出是:
    2 1 2 3 4 5 6 6 
    显然多了一次根节点和它的左子节点的交换。事实上,伪代码是:
    for i ← length[A] downto 2
    所以,Java代码应该就是 > 1,不能循环到0,0是根节点。
      

  5.   

    在堆排序时,如果数组长度是n,这需要调用n-1次heapify。
    而楼主写的代码,只调用了n-2次heapify。假设堆(array)只有2个元素,for(i = array.length/2;i>1;..),循环体内的元素就不会执行,导致排序失败。
    当然我也是粗心大意,提供的代码也不对,正确的代码是  public static <T> void heapSort(T[] a, Comparator<? super T> c) {
           buildHeap(a, c);
           for (int i = a.length - 1; i > 0; i--) {
               swap(a, 0, i);
               heapify(a, 0, c, i);
           }
       }
      

  6.   

    真是服了CSDN,竟然不能修改自己的帖子
      

  7.   


    我也不能编辑被回复过的这个帖子,正确的代码只能在blog里面改正了。
      

  8.   

    客气了,希望你能写更多Blog。对那些学习算法的人有帮助。