首页 > 编程语言 >「数组」堆排序 / 大根堆优化(C++)

「数组」堆排序 / 大根堆优化(C++)

时间:2024-09-15 18:20:25浏览次数:12  
标签:大根堆 arr idx int 堆排序 pos C++ 数组 size

目录

概述

核心概念:堆

堆结构

数组存堆

思路

算法过程

up()

down()

Code

优化方案

大根堆优化

Code(pro)

复杂度

总结


概述

「数组」快速排序 / 随机值优化|小区间插入优化(C++)中,我们介绍了三种基本排序中的冒泡排序与分治思想结合的算法:快速排序。

本文我们来讲第二种基本排序:选择排序与分治思想结合的产物:堆排序。

我们来回想选择排序:每次选出最小的元素放在数组头部位置,每次都扫描一遍整个数组,整体表现为O(n²)。

我们希望只进行少量比较就能得出数组中的最小元素,该怎么做呢?堆这种结构给了我们一点启发。


核心概念:堆

堆是一颗完全二叉树,它的特点是可以用一维数组来储存。

堆结构

在初学数组排序阶段就理解二叉树似乎有些困难,不过好在我们不必完全了解二叉树的所有概念。

我们只需要知道:

①一个堆是一个层状结构,除去最底一层,每层的每个节点都有左子节点和右子节点,层层布满。

节点从上到下,从左到右依次编号。

(对于这样的结构,我们称之为二叉树,每个父节点都有左右孩子指针指向子节点。) 

②只有最后一层允许节点不排满,但节点的排布仍然是严格从左到右的。

如下,图一和图二都是堆,但图三不是堆,因为它的最底层排布不是从左到右的。

 ③堆有两种:小根堆和大根堆。

小根堆要求父节点的值小于它的两个孩子,大根堆要求父节点的值大于它的两个孩子。

我们称二叉树的头结点为根,所以这种命名就很好理解了:小根堆的根最小,大根堆的根最大。

数组存堆

此时此刻我们完全不必知道二叉树的标准结构,因为数组就可以储存堆

观察:

我们发现,一个序号从0开始的堆结构,

对于第idx个节点:

父节点序号:(idx-1)/2。

左子节点序号:idx*2+1。

右子节点序号:idx*2+2。

也就是说,对于上图这样的堆,我们将它存入数组应该是这样的:

        i   0    1    2    3    4    5    6
int arr[i]  10   15   30   40   50   100  40

因此,对于一个堆,我们可以用数组来表示它。 


思路

堆这种结构只是为我们的选择排序优化服务的。

选择排序需要我们每次找到最小的元素,那么我们不妨对数组建堆(又称堆化),获得一个小根堆数组后,堆顶,也就是序号为0的数组位置,自然就是我们要的最小元素。

获得最小元素后堆顶出堆,对剩余元素重新堆化,堆顶每次都是剩余元素中的最小元素。

我们不断进行堆顶出堆,就实现了选择排序。 

考虑到堆化是按层实现的,因此若有n个元素,则有logn层,重新堆化的过程中内部重排最多进行logn次,通过logn次比较获得最小元素,这显然优于暴力选择排序。


算法过程

堆排序由两个操作构成:上浮up和下沉down。

我们先用宏定义描述一下节点父子关系,另有swap函数实现功能封装:

#define father(x) ((x-1)/2)
#define lchild(x) (2*x+1)
#define rchild(x) (2*x+2)
void swap(int& a, int& b) {
	int temp = b;
	b = a, a = temp;
}

up()

对数组进行初始堆化时,依靠上浮实现。

将堆的大小称为size,数组的整体长度称为len。

我们将数组arr分割成两部分:已经堆化的[0,size),未堆化的剩余部分[size,len)

我们将剩余部分的第一个数加入堆中,它显然处于堆底,为了让它处于小根堆中合适的位置,我们进行对它上浮操作。

int size = 0;
for (int i = 0; i < len; i++) {
	up(arr, i);
	size++;
}

当idx为0时,不再上浮,否则判断此节点与其父亲的大小关系。

我们维护小根堆,所以如果父节点较大,则两者进行交换,使得父节点较小。

然后跟踪父节点,对父节点继续执行上浮操作。(这里的递归操作顺理成章的出现了)

void up(int arr[], int idx) {
	if (idx && arr[father(idx)] > arr[idx]) {
		swap(arr[father(idx)], arr[idx]);
		up(arr, father(idx));
	}
}

down()

数组完全堆化后,我们开始进行堆顶出堆,实现选择排序。

我们使用小根堆,因此需要一个额外的辅助空间来承载结果(后续它会被我们的优化方案优化掉)。

堆顶出堆后将堆中的最后一个元素赋给堆顶,堆size缩小,然后开始对堆顶执行下沉操作。

int* assist = new int[len];
for (int j = 0; j < len; j++) {
	assist[j] = arr[0];
	arr[0] = arr[--size];
	down(arr,0,size);
}
memcpy(arr, assist, sizeof(int) * len);
delete[] assist;

定义pos,

①如果idx节点的左右孩子没有超出数组堆化范围,则pos等于左右孩子中较小的元素的索引,这是为了使得较小的元素总是位于堆的上部。

②如果idx的右孩子超出堆化范围,那么堆中只有左孩子是有效的,pos等于左孩子。

③如果idx的左孩子也超出堆化范围,说明idx已经在堆中沉底,没有后续元素,不必比较直接返回。

当pos位的元素小于idx位的元素时,两者作交换(即idx较大时,与其最小的子节点交换),然后跟踪pos,继续下沉。 

void down(int arr[], int idx, int size) {
	int pos;
	if (rchild(idx) < size)pos = arr[lchild(idx)] < arr[rchild(idx)] ? lchild(idx) : rchild(idx);
	else if (lchild(idx) < size)pos = lchild(idx);
	else return;
	if (arr[idx] > arr[pos]) {
		swap(arr[idx], arr[pos]);
		down(arr,pos,size);
	}
}

Code

#define father(x) ((x-1)/2)
#define lchild(x) (2*x+1)
#define rchild(x) (2*x+2)
void up(int arr[], int idx) {
	if (idx && arr[father(idx)] > arr[idx]) {
		swap(arr[father(idx)], arr[idx]);
		up(arr, father(idx));
	}
}
void down(int arr[], int idx, int size) {
	int pos;
	if (rchild(idx) < size)pos = arr[lchild(idx)] < arr[rchild(idx)] ? lchild(idx) : rchild(idx);
	else if (lchild(idx) < size)pos = lchild(idx);
	else return;
	if (arr[idx] > arr[pos]) {
		swap(arr[idx], arr[pos]);
		down(arr,pos,size);
	}
}
void heap_sort(int arr[], int len) {
	int size = 0;
	for (int i = 0; i < len; i++) {
		size++;
		up(arr, i);
	}
	int* assist = new int[len];
	for (int j = 0; j < len; j++) {
		assist[j] = arr[0];
		arr[0] = arr[--size];
		down(arr,0,size);
	}
	memcpy(arr, assist, sizeof(int) * len);
	delete[] assist;
}

优化方案

辅助数组assist看起来很愚蠢,我们来像个办法处理掉它。

大根堆优化

我们何不使用大跟堆来依次弹出数组的最大元素呢?

小根堆是从前往后进行最小值选择排序,因此无法安放在原始数组中(因为堆化部分会占据数组的前面部分),但大根堆解决了这个问题。

考虑到弹出时堆size收缩,因此数组的末尾会空出一个位置,我们可以直接将弹出元素安放到该位置上。

Code(pro)

#define father(x) ((x-1)/2)
#define lchild(x) (2*x+1)
#define rchild(x) (2*x+2)
void bigger_up(int arr[], int idx) {
	if (idx && arr[father(idx)] < arr[idx]) {
		swap(arr[father(idx)], arr[idx]);
		bigger_up(arr, father(idx));
	}
}
void smaller_down(int arr[], int idx, int size) {
	int pos;
	if (rchild(idx) < size)pos = arr[lchild(idx)] > arr[rchild(idx)] ? lchild(idx) : rchild(idx);
	else if (lchild(idx) < size)pos = lchild(idx);
	else return;
	if (arr[idx] < arr[pos]) {
		swap(arr[idx], arr[pos]);
		smaller_down(arr, pos, size);
	}
}
void HPsort(int arr[], int len) {
	int size = 0;
	for (int i = 0; i < len; i++,size++) 
		bigger_up(arr, i);
	while (size--) {
		swap(arr[0], arr[size]);
		smaller_down(arr, 0, size);
	}
}

*注意*:大根堆上浮大元素,沉底小元素。 


复杂度

时间复杂度:O(nlogn)

空间复杂度:O(logn)

复杂度分析

时间分析:{

考虑堆化是按层实现的,因此若有n个元素,则有logn层。

对n个元素建堆,每个元素按层上浮,最多比较logn次,得到O(nlogn)

对n个元素出堆,弹出堆顶后将堆尾赋给堆顶,每个元素按层下沉,最多比较logn次,得到O(nlogn)

O(nlogn)+O(nlogn)=O(2nlogn)=O(nlogn)。

}

空间分析:{

使用大跟堆建堆时,不使用额外空间承载答案。

建堆和出堆时调用递归函数进行压栈,函数最多调用logn层,最多占据空间O(logn)。

}


总结

堆为我们提供了一种新的视角来处理数组的最小元素,它的另一个重大用途就是实现优先队列priority_queue。

堆排序的分治策略也比较新颖:他不是在算法思想上进行分治,而是利用模拟堆这种数据结构进行分治,希望可以为你带来对分治思想的新启发。

标签:大根堆,arr,idx,int,堆排序,pos,C++,数组,size
From: https://blog.csdn.net/dakingffo/article/details/142285574

相关文章

  • 详解c++多态---上
    virtual关键字1.可以修饰原函数,为了完成虚函数的重写,满足多态的条件之一。classPerson{public:virtualvoidBuyTicket(){cout<<"买票-全价"<<endl;}};classStudent:publicPerson{public:virtualvoidBuyTicket(){cout<<"买票-半价"<<......
  • c++走出迷宫改良版2
    本文对上期做了删改话不多说上代码:注彩色输出部分代码出自博主夜若渊#include<bits/stdc++.h>#include<windows.h>#include<stdlib.h>#include<cstdio>#include<iostream>#include<string>#include<stdio.h>#include<ctime>#include<conio.h&g......
  • 深入解析C++函数指针:掌握游戏开发中的关键技术
    深入解析C++函数指针:掌握游戏开发中的关键技术C++作为一门经典的编程语言,因其强大的性能和灵活性,被广泛应用于游戏开发。而函数指针作为C++中的一个重要概念,在游戏开发中更是扮演着不可或缺的角色。对于想要深入掌握C++并在游戏开发领域站稳脚跟的开发者来说,理解并灵活运用函数指......
  • C++入门补充语法
    1、C和C++的区别                首先C++是包含C语言的,C语言中的所有语法在C++中都可以应用,因为C语言语法限制过多导致许多东西实现起来不方便,所以C++又制订了一系列的语法来补充C语言的不足。2、命名空间2.1命名空间为什么要使用命名空间,下面我们使用一段......
  • C++资源管理浅谈
    引言:            在计算机编程语言的学习与实践中,自然避免不了与计算机的资源管理打交道。所谓的资源就是,一旦用了它,将来就必须还给系统,如果用户不这么做,那糟糕的事情便会发生。在开始谈及C++的资源管理之前,先来聊聊何为计算机的资源,以及为何要管理计算机的资......
  • 【C++】string类中常用函数的模拟实现
    【C++】string类中常用函数的模拟实现1.string.h2.Text.cpp1.string.h#include<assert.h>namespacewch{ classstring { public: typedefchar*iterator; typedefconstchar*const_iterator; iteratorbegin() { return_str; } itera......
  • C++string容器
    string容器基本概念本质:string是C++风格的字符串,而string本质上是一个类string和char*区别:char*是一个指针string是一个类,类内部封装了char*,管理这个字符串,是一个char*型的容器特点:string类内部封装了很多成员方法例如:查找find,拷贝copy,删除delete替换replac......
  • C++: 二叉树进阶面试题
    做每件事之前都心存诚意,就会事半功倍.目录前言1.根据二叉树创建字符串2.二叉树的层序遍历Ⅰ3.二叉树的层序遍历Ⅱ4.二叉树的最近公共祖先5.二叉搜索树与双向链表6.根据一棵树的前序遍历与中序遍历构造二叉树7.根据一棵树的中序遍历与后序遍历构造二叉树8.二......
  • windows C++ 并行编程-并行容器和对象
    并行模式库(PPL)包括几个容器和对象,这些容器和对象提供对其元素的线程安全访问。并发容器提供对最重要操作的并发安全访问。在这里,并发安全意味着指针或迭代器始终有效。它不保证元素初始化或特定的遍历顺序。这些容器的功能与C++标准库提供的功能类似。例如,concurren......
  • windows C++-并行编程-PPL任务并行(一)
    在并发运行时中,任务是执行特定作业并通常与其他任务并行运行的工作单元。任务可以分解为组织成任务组的其他更细化的任务。编写异步代码,并希望在异步操作完成之后进行某种操作时,可使用任务。例如,可以使用一个任务以异步方式从文件读取,然后使用另一个任务(延续任务,本文档稍后......