堆排序演示

本文主要是介绍堆排序演示，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

上代码:

#include "common.h"

/**
* heap_size 此次调整堆的最大元素个数(因为堆排序过程中，后面已经调整好的就不需要调整了)
* i 表示此次调整堆的父节点
* */

typedef struct Heap
{
	int heap[100];
	int tail;
}Heap;

static int Compare(int ID1, int ID2)
{
	return ID1 - ID2;
}

//交换堆中任意两个数
static void Swap(Heap *pheap, int pos1, int pos2)
{
	int ID1 = pheap->heap[pos1];
	int ID2 = pheap->heap[pos2];
	pheap->heap[pos1] = ID2;
	pheap->heap[pos2] = ID1;
}

//打印堆中的数据
static void printHeap(Heap *pheap)
{
	for (int i = 1; i < pheap->tail; i++)
	{
		printf("%d ", pheap->heap[i]);
	}
	printf("\n\n");
}

#define parent (pos >> 1) //获得该父节点的左孩子
#define left   (pos << 1)   //获得该父节点的左孩子
#define right  (pos*2 + 1)  //获得该父节点的右孩子

static void adjustHeap(Heap *pheap, int pos) // heap_size --> tail
{
	if (pos <= 0)
	{
		return;
	}

	int old_pos = pos;

	while (pos > 1 && Compare(pheap->heap[parent], pheap->heap[pos]) < 0)
	{
		Swap(pheap, pos, parent);
		pos = parent;
	}

	pos = old_pos;

	while ((left < pheap->tail && Compare(pheap->heap[left], pheap->heap[pos]) > 0)
		|| (right < pheap->tail && Compare(pheap->heap[right], pheap->heap[pos]) > 0))
	{
		if ((left < pheap->tail && Compare(pheap->heap[left], pheap->heap[pos]) > 0)
			&& (right < pheap->tail && Compare(pheap->heap[right], pheap->heap[pos]) > 0))
		{
			if (Compare(pheap->heap[left], pheap->heap[right]) > 0) {
				Swap(pheap, pos, left);
				pos = left;
			}
			else
			{
				Swap(pheap, pos, right);
				pos = right;
			}
		}// tail == 12 的时候, pos = 6, 又跟已经交换到 12 的值为 18 的元素交换, 所以不能用 <=
		else if (left < pheap->tail && Compare(pheap->heap[left], pheap->heap[pos]) > 0)
		{
			Swap(pheap, pos, left);
			pos = left;
		}
		else if (right < pheap->tail && Compare(pheap->heap[right], pheap->heap[pos]) > 0)
		{
			Swap(pheap, pos, right);
			pos = right;
		}
	}
}

static void maxHeapInsert(Heap *pheap, int key)
{
	int old_pos = pheap->tail;
	pheap->heap[old_pos] = key;
	pheap->tail++;
	adjustHeap(pheap, old_pos);
}

extern void test_heap_qfh()
{
	//simple test
	int arr[] = { 20,14,10,8,7,9,3,2,4,1,80,50,40,70,11,19,12,18,23,35,22 };  // 这个不考虑 0 号元素， 可能好一点
	int len = sizeof(arr) / sizeof(arr[0]); // no need to consider number 0, so the len is 9 only
	printf("%s %d : arr len = %d \n", __FUNCTION__, __LINE__, len);

	Heap heap;
	heap.heap[0] = 0; // 源数组是有值的
	heap.tail = 1;

	LOGE("will build max heap");
	//build heap (插入式创建 heap)
	for (int i = 0; i < len; i++)
	{
		maxHeapInsert(&heap, arr[i]);
		printHeap(&heap);
	}

	LOGE("will sort all the heap");
	for (int heap_size = len; heap_size >= 2; heap_size--) // heap_size is size of not sort of heap , from tail-1 to 1
	{
		heap.tail--;
		Swap(&heap, 1, heap.tail);//将堆顶元素（通过调整堆获得的最大值）和最后一个交换（剩余未排好序部分的最后一个）
		adjustHeap(&heap, 1);//之后每次从堆顶开始调整，最大的值将上升到根节点
		printHeap(&heap);
	}
	heap.tail = len + 1;
	printHeap(&heap);
}

will build max heap  （构建最大堆的过程）：

20

20 14

20 14 10

20 14 10 8

20 14 10 8 7

20 14 10 8 7 9

20 14 10 8 7 9 3

20 14 10 8 7 9 3 2

20 14 10 8 7 9 3 2 4

20 14 10 8 7 9 3 2 4 1

80 20 10 8 14 9 3 2 4 1 7

80 20 50 8 14 10 3 2 4 1 7 9

80 20 50 8 14 40 3 2 4 1 7 9 10

80 20 70 8 14 40 50 2 4 1 7 9 10 3

80 20 70 8 14 40 50 2 4 1 7 9 10 3 11

80 20 70 19 14 40 50 8 4 1 7 9 10 3 11 2

80 20 70 19 14 40 50 12 4 1 7 9 10 3 11 2 8

80 20 70 19 14 40 50 12 18 1 7 9 10 3 11 2 8 4

80 23 70 20 14 40 50 12 19 1 7 9 10 3 11 2 8 4 18

80 35 70 20 23 40 50 12 19 14 7 9 10 3 11 2 8 4 18 1

80 35 70 20 23 40 50 12 19 22 7 9 10 3 11 2 8 4 18 1 14

will sort all the heap  （对大顶堆进行排序， 堆顶元素 heap[1] 是待排序列的最大值, 右边是已经拍好序的, 这里没有打印出来，

每次 heap[1] 跟堆尾元素进行交换 ， 堆堆中的某一个 heap[pos] 元素进行更新, 就需要对 pos 调用 adjustHeap 函数：

70 35 50 20 23 40 14 12 19 22 7 9 10 3 11 2 8 4 18 1

50 35 40 20 23 10 14 12 19 22 7 9 1 3 11 2 8 4 18

40 35 18 20 23 10 14 12 19 22 7 9 1 3 11 2 8 4

35 23 18 20 22 10 14 12 19 4 7 9 1 3 11 2 8

23 22 18 20 8 10 14 12 19 4 7 9 1 3 11 2

22 20 18 19 8 10 14 12 2 4 7 9 1 3 11

20 19 18 12 8 10 14 11 2 4 7 9 1 3

19 12 18 11 8 10 14 3 2 4 7 9 1

18 12 14 11 8 10 1 3 2 4 7 9

14 12 10 11 8 9 1 3 2 4 7

12 11 10 7 8 9 1 3 2 4

11 8 10 7 4 9 1 3 2

10 8 9 7 4 2 1 3

9 8 3 7 4 2 1

8 7 3 1 4 2

7 4 3 1 2

4 2 3 1

3 2 1

2 1

1

1 2 3 4 7 8 9 10 11 12 14 18 19 20 22 23 35 40 50 70 80

如果有主关键字和次关键字的情况, 如果一本书有 价格 和 ID 两种关键字, 则需要在 比较函数和交换函数增加代码处理, adjustHeap 函数可以保持通用  :

#include "common.h"
#include<time.h>

/*
如果要产生1~100，则是这样：int num = rand() % 100 + 1;
总结来说，可以表示为：int num = rand() % n + a;  其中的a是起始值，n - 1 + a是终止值，n是整数的范围。
一般性：rand() % (b - a + 1) + a;  就表示  a~b 之间的一个随机整数。
*/

// 每本书的 id 都不一样, 对书进行排序, 优先返回价格比较高的，如果价格一样, 则先返回id 小的
typedef struct Book
{
	int memidx; // 这样 id 的值就比较随意了
	int id;
	int price;
	int pos;
}Book;

#define maxbookcnt 20
static Book mbook[maxbookcnt];

void init_book(int num)
{
	srand((int)time(0));
	for (int i = 0; i < num; i++)
	{
		mbook[i].memidx = i;
		mbook[i].id = i; //次关键字
		//mbook[i].price = i + 100; //主关键字
		mbook[i].price = 1 + rand() % (100 - 10 + 1) + 10;
		printf("[%d %d] ", mbook[i].id, mbook[i].price);
	}
	printf("\n\n");
}

/**
* heap_size 此次调整堆的最大元素个数(因为堆排序过程中，后面已经调整好的就不需要调整了)
* i 表示此次调整堆的父节点
* */

typedef struct Heap
{
	int heap[maxbookcnt];
	int tail;
}Heap;

//比较堆中任意两个数, 价格越高, 排在前面, 如果价格一样，则ID 小的排在前面
static int Compare(int ID1, int ID2)
{
	if (mbook[ID1].price == mbook[ID2].price)
	{
		return ID2 - ID1;
	}

	return mbook[ID1].price - mbook[ID2].price;
}

//交换堆中任意两个数
static void Swap(Heap *pheap, int pos1, int pos2)
{
	int ID1 = pheap->heap[pos1];
	int ID2 = pheap->heap[pos2];
	pheap->heap[pos1] = ID2;
	pheap->heap[pos2] = ID1;

	mbook[ID1].pos = pos2;
	mbook[ID2].pos = pos1;
}

//打印堆中的数据
static void printHeap(Heap *pheap)
{
	for (int i = 1; i < pheap->tail; i++)
	{
		int id = pheap->heap[i];
		printf("[%d %d] ", mbook[id].id, mbook[id].price);
	}
	printf("\n\n");
}

#define parent (pos >> 1) //获得该父节点的左孩子
#define left   (pos << 1)   //获得该父节点的左孩子
#define right  (pos*2 + 1)  //获得该父节点的右孩子

static void adjustHeap(Heap *pheap, int pos) // heap_size --> tail
{
	if (pos <= 0)
	{
		return;
	}

	int old_pos = pos;

	while (pos > 1 && Compare(pheap->heap[parent], pheap->heap[pos]) < 0)
	{
		Swap(pheap, pos, parent);
		pos = parent;
	}

	pos = old_pos;

	while ((left < pheap->tail && Compare(pheap->heap[left], pheap->heap[pos]) > 0)
		|| (right < pheap->tail && Compare(pheap->heap[right], pheap->heap[pos]) > 0))
	{
		if ((left < pheap->tail && Compare(pheap->heap[left], pheap->heap[pos]) > 0)
			&& (right < pheap->tail && Compare(pheap->heap[right], pheap->heap[pos]) > 0))
		{
			if (Compare(pheap->heap[left], pheap->heap[right]) > 0) {
				Swap(pheap, pos, left);
				pos = left;
			}
			else
			{
				Swap(pheap, pos, right);
				pos = right;
			}
		}// tail == 12 的时候, pos = 6, 又跟已经交换到 12 的值为 18 的元素交换, 所以不能用 <=
		else if (left < pheap->tail && Compare(pheap->heap[left], pheap->heap[pos]) > 0)
		{
			Swap(pheap, pos, left);
			pos = left;
		}
		else if (right < pheap->tail && Compare(pheap->heap[right], pheap->heap[pos]) > 0)
		{
			Swap(pheap, pos, right);
			pos = right;
		}
	}
}

static void maxHeapInsert(Heap *pheap, int key)
{
	int old_pos = pheap->tail;
	pheap->heap[old_pos] = key;
	pheap->tail++;
	adjustHeap(pheap, old_pos);
}

extern void test_heap_book()
{
	int len = maxbookcnt;
	init_book(len);
	LOGE("book len = %d ", len);

	Heap heap;
	heap.heap[0] = 0;
	heap.tail = 1;

	LOGE("will build max heap");
	//build heap (插入式创建 heap)
	for (int i = 1; i < len; i++)
	{
		maxHeapInsert(&heap, mbook[i].id);
		printHeap(&heap);
	}

	LOGE("will sort all the heap");
	for (int heap_size = len; heap_size >= 2; heap_size--) // heap_size is size of not sort of heap , from tail-1 to 1
	{
		heap.tail--;
		Swap(&heap, 1, heap.tail);//将堆顶元素（通过调整堆获得的最大值）和最后一个交换（剩余未排好序部分的最后一个）
		adjustHeap(&heap, 1);//之后每次从堆顶开始调整，最大的值将上升到根节点
		printHeap(&heap);
	}
	heap.tail = len;
	printHeap(&heap);
}

书本排序过程 :

will build max heap (构造最大堆) : 
[1 22]

[2 44] [1 22]

[2 44] [1 22] [3 17]

[2 44] [4 41] [3 17] [1 22]

[5 90] [2 44] [3 17] [1 22] [4 41]

[6 93] [2 44] [5 90] [1 22] [4 41] [3 17]

[7 96] [2 44] [6 93] [1 22] [4 41] [3 17] [5 90]

[7 96] [2 44] [6 93] [8 24] [4 41] [3 17] [5 90] [1 22]

[9 99] [7 96] [6 93] [2 44] [4 41] [3 17] [5 90] [1 22] [8 24]

[9 99] [7 96] [6 93] [2 44] [4 41] [3 17] [5 90] [1 22] [8 24] [10 36]

[9 99] [7 96] [6 93] [2 44] [4 41] [3 17] [5 90] [1 22] [8 24] [10 36] [11 27]

[9 99] [7 96] [6 93] [2 44] [4 41] [12 55] [5 90] [1 22] [8 24] [10 36] [11 27] [3 17]

[9 99] [7 96] [6 93] [2 44] [4 41] [12 55] [5 90] [1 22] [8 24] [10 36] [11 27] [3 17] [13 40]

[9 99] [7 96] [6 93] [2 44] [4 41] [12 55] [14 93] [1 22] [8 24] [10 36] [11 27] [3 17] [13 40] [5 90]

[9 99] [7 96] [6 93] [2 44] [4 41] [12 55] [14 93] [1 22] [8 24] [10 36] [11 27] [3 17] [13 40] [5 90] [15 46]

[9 99] [7 96] [6 93] [16 59] [4 41] [12 55] [14 93] [2 44] [8 24] [10 36] [11 27] [3 17] [13 40] [5 90] [15 46] [1 22]

[9 99] [7 96] [6 93] [17 87] [4 41] [12 55] [14 93] [16 59] [8 24] [10 36] [11 27] [3 17] [13 40] [5 90] [15 46] [1 22] [2 44]

[9 99] [7 96] [6 93] [17 87] [4 41] [12 55] [14 93] [16 59] [18 77] [10 36] [11 27] [3 17] [13 40] [5 90] [15 46] [1 22] [2 44] [8 24]

[9 99] [7 96] [6 93] [17 87] [4 41] [12 55] [14 93] [16 59] [18 77] [10 36] [11 27] [3 17] [13 40] [5 90] [15 46] [1 22] [2 44] [8 24] [19 22]



will sort all the heap （每次跟队尾交换） :


[7 96] [17 87] [6 93] [18 77] [4 41] [12 55] [14 93] [16 59] [8 24] [10 36] [11 27] [3 17] [13 40] [5 90] [15 46] [1 22] [2 44] [19 22]

[6 93] [17 87] [14 93] [18 77] [4 41] [12 55] [5 90] [16 59] [8 24] [10 36] [11 27] [3 17] [13 40] [19 22] [15 46] [1 22] [2 44]

[14 93] [17 87] [5 90] [18 77] [4 41] [12 55] [15 46] [16 59] [8 24] [10 36] [11 27] [3 17] [13 40] [19 22] [2 44] [1 22]

[5 90] [17 87] [12 55] [18 77] [4 41] [13 40] [15 46] [16 59] [8 24] [10 36] [11 27] [3 17] [1 22] [19 22] [2 44]

[17 87] [18 77] [12 55] [16 59] [4 41] [13 40] [15 46] [2 44] [8 24] [10 36] [11 27] [3 17] [1 22] [19 22]

[18 77] [16 59] [12 55] [2 44] [4 41] [13 40] [15 46] [19 22] [8 24] [10 36] [11 27] [3 17] [1 22]

[16 59] [2 44] [12 55] [8 24] [4 41] [13 40] [15 46] [19 22] [1 22] [10 36] [11 27] [3 17]

[12 55] [2 44] [15 46] [8 24] [4 41] [13 40] [3 17] [19 22] [1 22] [10 36] [11 27]

[15 46] [2 44] [13 40] [8 24] [4 41] [11 27] [3 17] [19 22] [1 22] [10 36]

[2 44] [4 41] [13 40] [8 24] [10 36] [11 27] [3 17] [19 22] [1 22]

[4 41] [10 36] [13 40] [8 24] [1 22] [11 27] [3 17] [19 22]

[13 40] [10 36] [11 27] [8 24] [1 22] [19 22] [3 17]

[10 36] [8 24] [11 27] [3 17] [1 22] [19 22]

[11 27] [8 24] [19 22] [3 17] [1 22]

[8 24] [1 22] [19 22] [3 17]

[1 22] [3 17] [19 22]

[19 22] [3 17]

[3 17]

 

最终的排序结果 :

[3 17] [19 22] [1 22] [8 24] [11 27] [10 36] [13 40] [4 41] [2 44] [15 46] [12 55] [16 59] [18 77] [17 87] [5 90] [14 93] [6 93] [7 96] [9 99]

这篇关于堆排序演示的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！