使用 Java PriorityQueue 实现大顶堆和堆排序
最编程
2024-08-14 20:51:09
...
堆数据结构实际上是一种数组对象,是以数组的形式存储的,可是它能够被视为一颗全然二叉树,因此又叫二叉堆。堆分为下面两种类型:
大顶堆:父结点的值不小于其子结点的值,堆顶元素最大
小顶堆:父结点的值不大于其子结点的值,堆顶元素最小
堆排序的时间复杂度跟合并排序一样,都是O(nlgn),可是合并排序不是原地排序(原地排序:在排序过程中,仅仅有常数个元素是保存在数组以外的空间),合并排序的全部元素都被复制到另外的数组空间中去,而堆排序是一个原地排序算法。
1、在堆排序中,我们通常使用大顶堆来实现,因为堆在操作上是被看着一颗全然二叉树,所以其高度为lgn,堆结构上的一些操作的时间复杂度也一般是O(lgn)。
/*
* 算法导论 第六章 堆排序
* 堆数据结构的实际存储是作为一个顺序数组来保存的
* 对堆的操作是将它作为一个全然二叉树的结构来使用的
*
* 堆排序也是属于一种选择排序,只是相比简单选择排序(时间复杂度为O(n^2)),堆排序要快得多
* 堆排序分为下面几个步骤:
* 首先是建立大顶堆,即函数buildMaxHeap,建堆实际上是利用堆的最大化调整(maxHeapify)自底向上来实现的
* 然后是逐步将堆顶的最大元素交换到堆的结尾,堆的大小也不断缩小,然后再将堆最大化,从而实现排序
*
* 当中建堆的时间复杂度为O(n),堆的最大化调整时间复杂度为O(lgn),所以总的
* 时间复杂度是O(n*lgn+n),即O(nlgn)
*/
#include <iostream>
using namespace std;
void printArray(int arr[], int len);
void heapSort(int arr[], int len);
void maxHeapify(int arr[], int heapSize, int pos);
void buildMaxHeap(int arr[], int len);
void selectSort(int *arr, int len);
void exchange(int arr[], int i, int j);
int main()
{
int arr[] = {16, 14, 10, 8, 7, 9, 3, 2, 4, 1};
int len = sizeof(arr) / sizeof(arr[0]);
cout << "原数组:" << endl;
printArray(arr, len);
heapSort(arr, len);
//selectSort(arr, len);
cout << "排序后的数组:" << endl;
printArray(arr, len);
return 0;
}
void printArray(int arr[], int len)
{
for (int i=0; i<len; i++)
{
cout << arr[i] << " ";
}
cout << endl;
}
void heapSort(int arr[], int len)
{
buildMaxHeap(arr, len);
for (int i=len-1; i>0; i--)
{
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
maxHeapify(arr, i, 0);
}
}
void maxHeapify(int arr[], int heapSize, int pos)
{
int lPos = (pos + 1) * 2 - 1;
int rPos = (pos + 1) * 2;
int largest = pos;
if (lPos < heapSize && arr[lPos] > arr[largest])
largest = lPos;
if (rPos < heapSize && arr[rPos] > arr[largest])
largest = rPos;
if (largest != pos)
{
int temp = arr[pos];
arr[pos] = arr[largest];
arr[largest] = temp;
maxHeapify(arr, heapSize, largest);
}
}
void buildMaxHeap(int arr[], int len)
{
for (int i=len/2-1; i>=0; i--)
{
maxHeapify(arr, len, i);
}
}
/*
* 简单选择排序
* 每次经过 n-i 次比較,从序列中选出i之后的最小元素放在第 i 个位置,以此排序
* 时间复杂度为O(n^2)
*/
void selectSort(int *arr, int len)
{
for (int i=0; i<len; i++)
{
int minIndex = i;
for (int j=i+1; j<len; j++)
{
if (arr[j] < arr[minIndex])
minIndex = j;
}
if (minIndex != i)
{
exchange(arr, i, minIndex);
}
}
}
void exchange(int arr[], int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
2、堆结构能够用来实现优先级队列,优先级队列是一组元素构成的集合,能够从中取出最大或者最小的元素,堆是优先级队列的一种非常好的实现。通过堆,优先级队列上的随意操作能够再O(lgn)时间内实现。
3、习题6.5-8解答
/*
* 算法导论 第六章 习题6.5-8
*
* 将k个链表中的首元素取出来作为一个数组,构成一个最小堆,堆顶元素即为最小
* 每次将堆顶元素插入到新链表尾部,然后将该元素原来所在链表的下一元素取出放到堆顶
* 若该链表取完了,则直接将堆尾元素放到堆顶,并将堆的大小减1,调整堆,反复取出堆顶
* 最小元素插入到新链表,直到k个链表都为空了为止
*
* 时间复杂度分析:建堆为O(k),取出堆中最小元素为O(lgk),共取了n次
* 时间复杂度为O(k+nlgk)=O(nlgk)
*/
#include <iostream>
using namespace std;
typedef struct LinkNode
{
int key;
LinkNode *next;
} LinkNode;
LinkNode* createLink(int arr[], int len);
LinkNode* heapExtractMin(LinkNode* arr[], int &len);
void minHeapify(LinkNode* arr[], int heapSize, int pos);
void buildMinHeap(LinkNode* arr[], int len);
int main()
{
int k = 5, n = 20;
int arr1[3] = {11, 14, 67};
int arr2[2] = {5, 35};
int arr3[5] = {3, 8, 12, 25, 90};
int arr4[4] = {9, 21, 49, 73};
int arr5[6] = {1, 32, 33, 45, 53, 88};
LinkNode *link1 = createLink(arr1, 3);
LinkNode *link2 = createLink(arr2, 2);
LinkNode *link3 = createLink(arr3, 5);
LinkNode *link4 = createLink(arr4, 4);
LinkNode *link5 = createLink(arr5, 6);
/*
* 把堆定义成一个指针数组,须要注意指针数组与数组指针的差别
* 指针数组:定义的是一个数组,数组中的每个元素都是一个指针
* 数组指针:定义的是一个指针,这个指针指向一个数组
*/
//定义堆数组
LinkNode* heap[] = {link1, link2, link3, link4, link5};
buildMinHeap(heap, k);
//定义又一次排序后的链表
LinkNode *resultLink = heapExtractMin(heap, k);
LinkNode *beforeNode = resultLink;
while (beforeNode && n-- > 1)
{
LinkNode *node = heapExtractMin(heap, k);
beforeNode->next = node;
beforeNode = node;
}
while (resultLink)
{
cout << resultLink->key << " ";
LinkNode *node = resultLink;
resultLink = resultLink->next;
delete node;
}
cout << endl;
return 0;
}
LinkNode* createLink(int arr[], int len)
{
LinkNode *nextNode = NULL;
for (int i=len-1; i>=0; i--)
{
LinkNode *node = new LinkNode();
node->key = arr[i];
node->next = nextNode;
nextNode = node;
}
return nextNode;
}
LinkNode* heapExtractMin(LinkNode* arr[], int &len)
{
if (len < 1)
return NULL;
LinkNode *minNode = arr[0];
if (arr[0]->next)
{
arr[0] = arr[0]->next;
} else {
len--;
arr[0] = arr[len];
}
if (len > 1)
{
minHeapify(arr, len, 0);
}
return minNode;
}
void minHeapify(LinkNode* arr[], int heapSize, int pos)
{
int lPos = (pos + 1) * 2 - 1;
int rPos = (pos + 1) * 2;
int smallest = pos;
if (lPos < heapSize && arr[lPos]->key < arr[smallest]->key)
smallest = lPos;
if (rPos < heapSize && arr[rPos]->key < arr[smallest]->key)
smallest = rPos;
if (smallest != pos)
{
LinkNode* temp = arr[pos];
arr[pos] = arr[smallest];
arr[smallest] = temp;
minHeapify(arr, heapSize, smallest);
}
}
void buildMinHeap(LinkNode* arr[], int len)
{
for (int i=len/2-1; i>=0; i--)
{
minHeapify(arr, len, i);
}
}
下一篇: C++实现的大顶堆和小顶堆的堆排序算法
推荐阅读
-
C++实现的大顶堆和小顶堆的堆排序算法
-
使用 Java PriorityQueue 实现大顶堆和堆排序
-
使用Python中的大顶堆heap实现堆排序算法
-
实现大顶堆的Java PriorityQueue实例
-
堆排序中 Go 语言中使用大顶堆和小顶堆的方法
-
《排序算法》——Java中的堆排序(大顶堆和小顶堆)
-
【Netty】「萌新入门」(七)ByteBuf 的性能优化-堆内存的分配和释放都是由 Java 虚拟机自动管理的,这意味着它们可以快速地被分配和释放,但是也会产生一些开销。 直接内存需要手动分配和释放,因为它由操作系统管理,这使得分配和释放的速度更快,但是也需要更多的系统资源。 另外,直接内存可以映射到本地文件中,这对于需要频繁读写文件的应用程序非常有用。 此外,直接内存还可以避免在使用 NIO 进行网络传输时发生数据拷贝的情况。在使用传统的 I/O 时,数据必须先从文件或网络中读取到堆内存中,然后再从堆内存中复制到直接缓冲区中,最后再通过 SocketChannel 发送到网络中。而使用直接缓冲区时,数据可以直接从文件或网络中读取到直接缓冲区中,并且可以直接从直接缓冲区中发送到网络中,避免了不必要的数据拷贝和内存分配。 通过 ByteBufAllocator.DEFAULT.directBuffer 方法来创建基于直接内存的 ByteBuf: ByteBuf directBuf = ByteBufAllocator.DEFAULT.directBuffer(16); 通过 ByteBufAllocator.DEFAULT.heapBuffer 方法来创建基于堆内存的 ByteBuf: ByteBuf heapBuf = ByteBufAllocator.DEFAULT.heapBuffer(16); 注意: 直接内存是一种特殊的内存分配方式,可以通过在堆外申请内存来避免 JVM 堆内存的限制,从而提高读写性能和降低 GC 压力。但是,直接内存的创建和销毁代价昂贵,因此需要慎重使用。 此外,由于直接内存不受 JVM 垃圾回收的管理,我们需要主动释放这部分内存,否则会造成内存泄漏。通常情况下,可以使用 ByteBuffer.clear 方法来释放直接内存中的数据,或者使用 ByteBuffer.cleaner 方法来手动释放直接内存空间。 测试代码: public static void testCreateByteBuf { ByteBuf buf = ByteBufAllocator.DEFAULT.buffer(16); System.out.println(buf.getClass); ByteBuf heapBuf = ByteBufAllocator.DEFAULT.heapBuffer(16); System.out.println(heapBuf.getClass); ByteBuf directBuf = ByteBufAllocator.DEFAULT.directBuffer(16); System.out.println(directBuf.getClass); } 运行结果: class io.netty.buffer.PooledUnsafeDirectByteBuf class io.netty.buffer.PooledUnsafeHeapByteBuf class io.netty.buffer.PooledUnsafeDirectByteBuf 池化技术 在 Netty 中,池化技术指的是通过对象池来重用已经创建的对象,从而避免了频繁地创建和销毁对象,这种技术可以提高系统的性能和可伸缩性。 通过设置 VM options,来决定池化功能是否开启: -Dio.netty.allocator.type={unpooled|pooled} 在 Netty 4.1 版本以后,非 Android 平台默认启用池化实现,Android 平台启用非池化实现; 这里我们使用非池化功能进行测试,依旧使用的是上面的测试代码 testCreateByteBuf,运行结果如下所示: class io.netty.buffer.UnpooledByteBufAllocator$InstrumentedUnpooledUnsafeDirectByteBuf class io.netty.buffer.UnpooledByteBufAllocator$InstrumentedUnpooledUnsafeHeapByteBuf class io.netty.buffer.UnpooledByteBufAllocator$InstrumentedUnpooledUnsafeDirectByteBuf 可以看到,ByteBuf 类由 PooledUnsafeDirectByteBuf 变成了 UnpooledUnsafeDirectByteBuf; 在没有池化的情况下,每次使用都需要创建新的 ByteBuf 实例,这个操作会涉及到内存的分配和初始化,如果是直接内存则代价更为昂贵,而且频繁的内存分配也可能导致内存碎片问题,增加 GC 压力。 使用池化技术可以避免频繁内存分配带来的开销,并且重用池中的 ByteBuf 实例,减少了内存占用和内存碎片问题。另外,池化技术还可以采用类似 jemalloc 的内存分配算法,进一步提升分配效率。 在高并发环境下,池化技术的优点更加明显,因为内存的分配和释放都是比较耗时的操作,频繁的内存分配和释放会导致系统性能下降,甚至可能出现内存溢出的风险。使用池化技术可以将内存分配和释放的操作集中到预先分配的池中,从而有效地降低系统的内存开销和风险。 内存释放 当在 Netty 中使用 ByteBuf 来处理数据时,需要特别注意内存回收问题。 Netty 提供了不同类型的 ByteBuf 实现,包括堆内存(JVM 内存)实现 UnpooledHeapByteBuf 和堆外内存(直接内存)实现 UnpooledDirectByteBuf,以及池化技术实现的 PooledByteBuf 及其子类。 UnpooledHeapByteBuf:通过 Java 的垃圾回收机制来自动回收内存; UnpooledDirectByteBuf:由于 JVM 的垃圾回收机制无法管理这些内存,因此需要手动调用 release 方法来释放内存; PooledByteBuf:使用了池化机制,需要更复杂的规则来回收内存; 由于池化技术的特殊性质,释放 PooledByteBuf 对象所使用的内存并不是立即被回收的,而是被放入一个内存池中,待下次分配内存时再次使用。因此,释放 PooledByteBuf 对象的内存可能会延迟到后续的某个时间点。为了避免内存泄漏和占用过多内存,我们需要根据实际情况来设置池化技术的相关参数,以便及时回收内存; Netty 采用了引用计数法来控制 ByteBuf 对象的内存回收,在博文 「源码解析」ByteBuf 的引用计数机制 中将会通过解读源码的形式对 ByteBuf 的引用计数法进行深入理解; 每个 ByteBuf 对象被创建时,都会初始化为1,表示该对象的初始计数为1。 在使用 ByteBuf 对象过程中,如果当前 handler 已经使用完该对象,需要通过调用 release 方法将计数减1,当计数为0时,底层内存会被回收,该对象也就被销毁了。此时即使 ByteBuf 对象还在,其各个方法均无法正常使用。 但是,如果当前 handler 还需要继续使用该对象,可以通过调用 retain 方法将计数加1,这样即使其他 handler 已经调用了 release 方法,该对象的内存仍然不会被回收。这种机制可以有效地避免了内存泄漏和意外访问已经释放的内存的情况。 一般来说,应该尽可能地保证 retain 和 release 方法成对出现,以确保计数正确。
-
使用Java实现和应用小顶堆和大顶堆:力扣347题目前K个高频元素的解答