学步园

堆排序实现：

#define LEFT(i) (2*i)
#define RIGHT(i) (2*i+1)
#define PARENT(i) (i/2)

template <typename T>
void heap_print(T seq[],int n)
{
    int h=floor(log(double(n))/log(2.))+1;
    for(int i=1;i<=h;i++)
    {
        for(int j=0;j<h-i;j++)
            cout<<"/t";
        for(int j=pow(2.,i-1);j<pow(2.,i) && j<n;j++)
            cout<<seq[j-1]<<"/t";
        cout<<endl;
    }
}

template <typename T>
void heap_maxify(T seq[],int n,int index)
{
    assert(index<=n);
    int leftindex=LEFT(index);
    int rightindex=RIGHT(index);
    int largestone=index;
    if(leftindex<=n && seq[leftindex-1]>seq[largestone-1])
        largestone=leftindex;
    if(rightindex<=n && seq[rightindex-1]>seq[largestone-1])
        largestone=rightindex;
    if(largestone!=index)
    {
        T temp=seq[index-1];
        seq[index-1]=seq[largestone-1];
        seq[largestone-1]=temp;
        heap_maxify(seq,n,largestone);
    }
}

template <typename T>
void heap_create(T seq[],int n)
{
    int partion=n/2;
    for(int i=partion;i>=1;i--)
        heap_maxify(seq,n,i);
}

template <typename T>
void heap_sort(T seq[],int n)
{
    heap_create(seq,n);
    for(int i=n;i>=2;i--)
    {
        T temp=seq[i-1];
        seq[i-1]=seq[0];
        seq[0]=temp;
        heap_maxify(seq,i-1,1);
    }
}

基于堆的K路合并问题：

题：请给出一下时间为O(n*lgk),用来将 k 个已排序链表合并为一个排序链表的算法.此处,n 次所有输入链表中元素的总数.

答：新建一个链表，再申请一个大小为 k 的数组A,首先把　k 个已排序链表的第一个元素压入 A 中，将 A 建成一个最小堆，花费O(k) 的时间．然后将堆 A 的第一个元素 min（也就是最小的那个）放入链表中．再将min->nextNode 放在min的位置．再花O(lgk)调用heapify 方法将 A 重新建成一个最小堆．然后又将第一个元素 min 放入链表......重复进行就可将 k 个已排序链表合并．（当最后剩余不到 k 个节点时情况会有点变化，但很容易解决）．显然，这样处理的时间复杂为 O(n*lgk);

Young 氏矩阵的相关算法：

      感觉杨氏矩阵（Young Tableau）是一个很奇妙的数据结构，他类似于堆的结构，又类似于BST的结构，对于查找某些元素，它优于堆；对于插入、删除它比BST更方便。

首先介绍一下这个数据结构的定义，Young Tableau有一个m*n的矩阵，让后有一数组 a[k], 其中 k<=m*n ，然后把a[k]中的数填入 m*n 的矩阵中，填充规则为（如图1-1）：

1.  每一行每一列都严格单调递增（有其他的版本是递减，其原理相同）。

2.  如果将a[k]中的数填完后，矩阵中仍有空间，则填入 ∞。

图1-1

则现在讨论，这个数据结构的几种操作，而在这些操作中，我们会发现堆排序的影子，并且这些操作具有很好的时间复杂度。

条件：一个已经建好的杨氏矩阵（Young Tableau）

操作：

【1】 在杨氏矩阵中插入元素x ---- Insert(x)

【2】  在杨氏矩阵中删除位于 (x, y) 位置的元素---- Delete(x, y)

【3】  返回x是否在矩阵中----Find(x)

其中1-2操作类似于堆的操作，而4操作类似于BST的操作。下面我就用我

自己的理解把这几个操作加以解释。

【1】 插入操作

本操作的时间复杂度为O( n + m ),其操作类似于堆排序的SIFT-UP算法。它的堆的结构在这里表现为某个元素Y[x, y] 下面和右面的两个元素 Y[x, y+1] ,Y[x+1, y]均比Y[x, y]要大。于是其插入算法可以描述为，首先把待插入元素以行为主序置于所有有效数字（除了无穷以外的数）最后面，如将x=2，放入 图1-1 的d5的位置，然后执行类似于SIFT-UP的操作，将x与它左边（记为x-l）及上面（记为x-u）的数进行比较，根据比较结果有三种可能的操作：

1：x-u > x 且x-u >= x-l  则将x 与 x-u进行交换

2：x-l > x 且x-l > x-u  则将x 与 x-l进行交换

3: x >= x-l 且 x > x-u  则x 不动，此时已经插入成功

（可以有其他合理的约定）

对例子插入2进行操作如图1-2箭头的操作方向。

图1-2

   由上述的操作知其时间复杂度最大为行列之和，即O(m+n)。

【2】 删除操作

操作类似于插入操作，其时间复杂度也为O(m+n)。其操作类似于堆排序的SIFT-DOWN算法。删除算法可以描述为，首先将删除的位置(x, y)的数字删除，然后调整，把杨氏矩阵中的最大值k（可以行为主序进行搜索到最后）填入到被删除位置，然后让此数与其下面的数(k-d)和右面的数进行(k-r)比较,此时比较结果为两种，因为此时元素一定会下移：

  1：k-d > k-r 将k-r 和 k进行交换

  2：k-d < k-r 将k-d 和 k进行交换

举例 删除图1-1的a3位置的元素5如图1-3