October 19, 2006

Scheme数据结构——向量也疯狂

学过数据结构的人都知道,一棵完全二叉树(除去最低层元素从左到右排列,其它的层都为满的)可以保存在一个数组中 这个完全二叉树存储在vector中就像这样:#(4 6 2 8 7 3) 可以看出一个结点下标 i 与它的左右孩子结点下标 j1,j2具有如下关系: j2 = 2*i+1,j2 = 2*i +2 然后,我们通过调整数组上结点的排列,把它变成一个“二叉堆”。这里显示的是一个最大堆,即:对于(vector-length a) => n,当(< (+ (* 2 i) 1) n) => #t时,有(> (vector-ref a (+ (* 2 i) 1)) (vector-ref a i) => #t;当(< (+ (* 2 i) 2) n) => #t时,有(> (vector-ref a (+ (* 2 i) 2)) (vector-ref a i) => #t。
这么复杂的S-exp,说白了,就是每个结点的左右孩子结点(如果有的话)都小于这个结点。 知道了这些,我们就可以来考虑一下怎么把完全二叉树转成最大堆了。方法是,先根据公式求出第一个非叶结点下标(define n (/ (- n 1) 2)),然后比较左孩子结点(vector-ref a (+ (* 2 i)与右孩子结点(vector-ref a (+ (* 2 i)的大小,将较大者与(vector-ref a i)比较,如果更大就互换。然后对于(- i 1),(- i 2)完成以上步骤,于是,最大堆就构造完成了。
  • 调整结点8:

  • 调整结点3:
  • 调整结点8:最后,最大堆有什么用呢?废话,当然是堆排序了;我最喜欢的排序算法就是它,因为它充分体现了“数形结合”的思想。 因为排序过程中整个堆都在大规模地变化(当然反应到数组上不是这么回事),所有就不再进行图解了;大致将一下即可:先将整个vector调整为最大堆,然后将堆顶的那个最大的元素与堆中最后一个元素互换,接着调整前 (- n 1) 个元素为最大堆,再将堆顶元素与堆中最后一个元素互换。。。如此反复(其实就是逐个排出最大元素),时间复杂度为O(n*log2 n)。
大致代码(缺少heep的实现):
(define (heep-sort a)
(let* ((n (vector-length a))(tmp 0) (i (- n 1)))

(begin
(make-heep a) ;调整a为最大堆
(when (> i 0)
(set! tmp (vector-ref a 0))
(vector-set! a 0 (vector-ref a 1))

(vector-set! a 1 tmp)
(heep a i 0) ;在向量a上从下标0开始调整长度为i的一段为最大堆
(set! i (- i 1)))))) ;最好用尾递归代替循环

No comments: