三叉堆排序（递归&非递归）

问题描述

输入：第一行是一个整数n，表示三叉堆节点的数量

第二行是n个整数，依次表示三叉堆节点的关键字。

输出：n行

每行若干个数，第一个数为树根（即数列最小值），之后若干个数依次为删除树根并用末尾节点关键字last代替根节点后每次交换的数，最后用关键字last结尾。

样例输入：

10 30 13 16

样例输出：

10 13 16

13 16

16 30

递归版本

上代码

#include 
   
    #include 
    
     void adjust(int* tritree, int tsize,int root){
   	int min = tritree[root];	int key = -1;	for (int i = 1; i <= 3; i++)	{
   		int curr = root * 3 + i;		if (curr > tsize)			break;		else		{
   			if (tritree[curr] < min)			{
   				min = tritree[curr];				key = curr;			}		}	}	if (key != -1)	{
   		tritree[key] = tritree[root];		tritree[root] = min;		printf_s("%d", min);		printf_s(" ");	}	for (int i = 1; i <= 3; i++)	{
   		if (root * 3 + i > tsize)			break;		else		{
   			adjust(tritree, tsize, root * 3 + i);		}	}}int main(){
   	int n;	scanf_s("%d", &n);	int* arry = (int*)calloc(n, sizeof(int));	for (int i = 0; i < n; i++)		scanf_s("%d", &arry[i]);	int size = n;	for (int i = 0; i < n; i++)	{
   		printf_s("%d", arry[0]);		printf_s(" ");		if (size != 1)		{
   			arry[0] = arry[size - 1];			size--;			adjust(arry, size, 0);			printf_s("%d", arry[size]);			printf_s("\n");		}	}}

核心函数就是堆调整函数adjust。注意，交换的条件是父节点的关键字大于三个孩子节点关键字的最小者，且交换的双方是父节点与三个孩子节点中的最小者。

很不幸，递归算法比较耗时，于是转而研究非递归算法。

非递归法

上代码

#include 
   
    #include 
    
     void adjust(int* tritree, int tsize,int root){
   	int Min = tritree[root];	int parent = root;	int left = 3 * parent + 1;	while (left < tsize)	{
   		if (left + 2 < tsize)//3 sons		{
   			int min = Min;			int key = -1;			for (int i = 0; i < 3; i++)			{
   				if (min > tritree[left + i])				{
   					min = tritree[left + i];					key = left + i;				}			}			if (key == -1)				break;			else			{
   				int tmp = tritree[key];				tritree[key] = tritree[parent];				tritree[parent] = tmp;				printf_s("%d", tmp);				printf_s(" ");				parent = key;				left = 3 * parent + 1;			}		}		else if (left + 1 < tsize)//2 sons		{
   			int key = -1;			int min = Min;			for (int i = 0; i < 2; i++)			{
   				if (min > tritree[left + i])				{
   					min = tritree[left + i];					key = left + i;				}			}			if (key == -1)				break;			else			{
   				int tmp = tritree[key];				tritree[key] = tritree[parent];				tritree[parent] = tmp;				printf_s("%d", tmp);				printf_s(" ");				parent = key;				left = 3 * parent + 1;			}		}		else//1 son		{
   			int min = Min;			if (min < tritree[left])				break;			else			{
   				tritree[parent] = tritree[left];				tritree[left] = min;				printf_s("%d", tritree[parent]);				printf_s(" ");				parent = left;				left = 3 * parent + 1;			}		}	}}int main(){
   	int n;	scanf_s("%d", &n);	int* arry = (int*)calloc(n, sizeof(int));	for (int i = 0; i < n; i++)		scanf_s("%d", &arry[i]);	int size = n;	for (int i = 0; i < n; i++)	{
   		printf_s("%d", arry[0]);		printf_s(" ");		if (size != 1)		{
   			arry[0] = arry[size - 1];			size--;			adjust(arry, size, 0);			printf_s("%d", arry[size]);			printf_s("\n");		}	}}

可以看到，非递归法只是修改了adjust函数。

一个关键点是：在一次调整的过程中，每次交换时，父节点一直都是这次调整最开始那个根节点（也就是从末尾拿出来替换根节点的那个关键字）。

题外话

三叉堆的性能将对于二叉堆有很大提升，详情请看这篇文章：

完

转载地址：http://pkwai.baihongyu.com/

你可能感兴趣的文章