数据结构与算法习题 replacement selection sort(置换选择排序)

数据结构与算法习题 replacement selection sort(置换选择排序)

Time Limit: 1000ms Memory Limit: 65536kB
Description
Given an original run made up of intergers, and a binary minimumheap，you are required touse the heap to implement the replacement selection sort, and output the firstrun. For example, given a run of 29,14,35,13 and a heap(marked as16,19,31,25,21,56,40), the first run got by using replacement selection sort will be 16,19,21,25.

Input
The first line contains two intergers m and n, m is the number of the elements of the original run, n is the size of the binary minimum heap.
The second line contains m intergers, that is the original run.
The third line contains n intergers, the elements of the heap that has been constructed(in order, from the top of the heap to the bottom of the heap, from left to right)
Output
The output contains one line, the first run.

Sample Input

4 7
29 14 35 13
16 19 31 25 21 56 40

Sample Output

16 19 21 25

---

本题对应外排序中的置换选择排序方法。
置换选择排序方法是:先把缓存区的数据建立一个堆，再从输入流读入数据，如果缓存区未满则直接放入缓存区，并调整为堆，否则从缓存区输出堆中的最值元素到输出流中。此时输入数据如果有可能和已经输出的构成顺串则插入缓存区输出流空出的空位中并调整，否则将缓存区堆的最后一个元素换到根结点再调整堆，而将这个元素放到缓存区的堆外，也就是说堆的大小减少一。这样知道堆为空，那么已经输出了一个顺串。将缓存区重建堆开始下一轮产生顺串即可。本题代码模拟了这一行为。

---

Accepted    2184kB  2ms 861 B   G++

#include<stdio.h>

const int SIZE=1000000;
const int INF=0x7FFFFFFF;

int buffer[SIZE],input[SIZE];
int size,last;

void sift(int i)
{
int l=2*i+1,r=2*i+2;
int vl=l<size?buffer[l]:INF,vr=r<size?buffer[r]:INF,v=buffer[i];
if (v<vl && v<vr)
return;
if (vl<vr)
    {
        buffer[i]=vl;
        buffer[l]=v;
        sift(l);
    }
else
    {
        buffer[i]=vr;
        buffer[r]=v;
        sift(r);
    }
return;
}

int main()
{
int m,n;
    scanf("%d%d",&m,&n);
for (int i=0;i<m;i++)
        scanf("%d",&input[i]);
for (int i=0;i<n;i++)
        scanf("%d",&buffer[i]);
    size=n;
last=-INF-1;
for (int i=(n-1)/2;i>=0;i--)
        sift(i);
for (int i=0;(i<m)&&(size);i++)
    {
last=buffer[0];
if (i!=0)
printf(" "); 
printf("%d",buffer[0]);
if (input[i]<last)
        {
            buffer[0]=buffer[size-1];
            buffer[size-1]=input[i];
            size--;
        }
else
            buffer[0]=input[i];
        sift(0);
    }
printf("\n");
return 0;
}