Java教程
堆排序演示
本文主要是介绍堆排序演示，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！
上代码:
#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]
这篇关于堆排序演示的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
-
Java中定时任务实现方式及源码剖析11-24
-
Java中定时任务实现方式及源码剖析11-24
-
鸿蒙原生开发手记：03-元服务开发全流程（开发元服务，只需要看这一篇文章）11-24
-
细说敏捷：敏捷四会之每日站会11-24
-
Springboot应用的多环境打包入门11-23
-
Springboot应用的生产发布入门教程11-23
-
Python编程入门指南11-23
-
Java创业入门：从零开始的编程之旅11-23
-
Java创业入门：新手必读的Java编程与创业指南11-23
-
Java对接阿里云智能语音服务入门详解11-23
-
Java对接阿里云智能语音服务入门教程11-23
-
JAVA对接阿里云智能语音服务入门教程11-23
-
Java副业入门：初学者的简单教程11-23
-
JAVA副业入门：初学者的实战指南11-23
-
JAVA项目部署入门：新手必读指南11-23
栏目导航
