邯郸市城市建设局网站百度竞价排名广告定价鲜花

邯郸市城市建设局网站,百度竞价排名广告定价鲜花,建站套餐,手机网页翻译#x1f3e0; 个人主页: EXtreme35 #x1f4da; 个人专栏: 专栏名称专栏主题简述《C语言》C语言基础、语法解析与实战应用《数据结构》线性表、树、图等核心数据结构详解《题解思维》算法思路、解题技巧与高效编程实践目录引言I. 堆操作的时间复杂度分析1. 堆的基本性质与… 个人主页:EXtreme35 个人专栏:专栏名称专栏主题简述《C语言》C语言基础、语法解析与实战应用《数据结构》线性表、树、图等核心数据结构详解《题解思维》算法思路、解题技巧与高效编程实践目录引言I. 堆操作的时间复杂度分析1. 堆的基本性质与高度1. 向上调整AdjustUp的建堆时间复杂度O ( N log ⁡ N ) O(N \log N)O(NlogN)2. 向下调整AdjustDown的建堆时间复杂度O ( N ) O(N)O(N)II. Top-K 问题1. 核心策略2.Top-K 问题的时间复杂度分析III. 总结引言堆Heap是一种特殊的完全二叉树数据结构通常用于实现优先队列。堆的性质要求在大顶堆中任意节点的值都大于或等于其子节点的值在小顶堆中任意节点的值都小于或等于其子节点的值。堆排序Heap Sort是基于堆这种数据结构的一种高效排序算法其核心操作在于元素的向上调整AdjustUp和向下调整AdjustDown这两种操作对于维护堆的性质至关重要。本文将首先深入探究堆排序中向上调整和向下调整操作的时间复杂度通过详细的数学分析证明其效率。随后我们将利用堆的特性结合您提供的 C 语言代码详细阐述和实现一个经典的算法问题——Top-K 问题即从一个大规模数据集中找出最大的 K 个元素。I. 堆操作的时间复杂度分析在堆中向上调整和向下调整操作是维持堆性质的基础尤其在插入元素向上调整和删除堆顶元素向下调整时。1. 堆的基本性质与高度一个包含N NN个元素的完全二叉树即堆的高度H HH是O ( log ⁡ N ) O(\log N)O(logN)。H ⌊ log ⁡ 2 N ⌋ H \lfloor \log_2 N \rfloorH⌊log2​N⌋证明假设一个满二叉树有N NN个节点其高度为H HH(根节点所在的层记为第 1 层则叶子节点在第H − 1 H-1H−1层)。则节点总数N NN满足N 1 2 4 ⋯ 2 H-1 2 H − 1 N 1 2 4 \dots 2^\text{H-1} 2^{H} - 1N124⋯2H-12H−1解出H HH:N 1 2 H 1 N1 2^{H1}N12H1→ \rightarrow→log ⁡ 2 ( N 1 ) H 1 \log_2(N1) H1log2​(N1)H1→ \rightarrow→H log ⁡ 2 ( N 1 ) H \log_2(N1)Hlog2​(N1)对于一个具有N NN个节点的完全二叉树其节点数N NN满足2 H ≤ N ≤ 2 H 1 − 1 2^H \le N \le 2^{H1} - 12H≤N≤2H1−1其中H HH是其高度最高层的索引。从左侧不等式2 H ≤ N 2^H \le N2H≤N可得H ≤ log ⁡ 2 N H \le \log_2 NH≤log2​N从右侧不等式N ≤ 2 H 1 − 1 N \le 2^{H1} - 1N≤2H1−1可得N 1 ≤ 2 H 1 → log ⁡ 2 ( N 1 ) ≤ H 1 → H ≥ log ⁡ 2 ( N 1 ) − 1 N1 \le 2^{H1} \rightarrow \log_2(N1) \le H1 \rightarrow H \ge \log_2(N1) - 1N1≤2H1→log2​(N1)≤H1→H≥log2​(N1)−1综合这两个不等式完全二叉树的高度H HH满足log ⁡ 2 ( N 1 ) − 1 ≤ H ≤ log ⁡ 2 N \log_2(N1) - 1 \le H \le \log_2 Nlog2​(N1)−1≤H≤log2​N因此对于足够大的N NN堆的高度H HH渐进地趋近于log ⁡ 2 N \log_2 Nlog2​N记为O ( log ⁡ N ) O(\log N)O(logN)。1. 向上调整AdjustUp的建堆时间复杂度O ( N log ⁡ N ) O(N \log N)O(NlogN)向上调整操作用于在堆尾插入一个新元素后恢复堆的性质。新元素位于子节点位置通过与其父节点比较如果新元素不满足堆的性质例如在小顶堆中子节点小于父节点则交换它们的位置并继续向上比较直到根节点或满足堆性质为止。操作过程分析比较与交换循环内比较a[child]和a[parent]若a[child] a[parent]则执行一次交换操作。移动交换后child变为原来的parentparent重新计算为新的(child - 1) / 2。在每一次循环中元素至多向上移动一层即操作次数 ≤ 1 \text{操作次数} \le 1操作次数≤1移动距离 1 层 \text{移动距离} 1 \text{ 层}移动距离1层该过程从叶子节点最深层H HH开始一直向上追溯到根节点。最坏情况是元素从最底层一直移动到根节点路径长度恰好等于堆的高度H HH。推导过程为简化计算我们以h hh层满二叉树为例进行分析若规定根结点层数为 1。则第i ii层的结点数n i 2 i − 1 n_i 2^{i-1}ni​2i−1该层结点向上调整的最大移动层数为i − 1 i-1i−1总移动步数T ( h ) T(h)T(h)是每层结点个数 * 向上调整次数第⼀层调整次数为0T ( h ) ∑ i 1 h 2 i − 1 ⋅ ( i − 1 ) T(h) \sum_{i1}^{h} 2^{i-1} \cdot (i-1)T(h)i1∑h​2i−1⋅(i−1)展开求和项并令j i − 1 j i-1ji−1:T ( h ) ∑ j 0 h − 1 2 j ⋅ j 2 1 ⋅ 1 2 2 ⋅ 2 2 3 ⋅ 3 ⋯ 2 h − 1 ⋅ ( h − 1 ) ( 1 ) T(h) \sum_{j0}^{h-1} 2^j \cdot j 2^1 \cdot 1 2^2 \cdot 2 2^3 \cdot 3 \dots 2^{h-1} \cdot (h-1) \quad (\text{1})T(h)j0∑h−1​2j⋅j21⋅122⋅223⋅3⋯2h−1⋅(h−1)(1)使用错位相减法。将(1) \text{(1)}(1)式乘以公比r 2 r2r2:2 ⋅ T ( h ) 2 2 ⋅ 1 2 3 ⋅ 2 2 4 ⋅ 3 ⋯ 2 h − 1 ⋅ ( h − 2 ) 2 h ⋅ ( h − 1 ) ( 2 ) 2 \cdot T(h) 2^2 \cdot 1 2^3 \cdot 2 2^4 \cdot 3 \dots 2^{h-1} \cdot (h-2) 2^h \cdot (h-1) \quad (\text{2} )2⋅T(h)22⋅123⋅224⋅3⋯2h−1⋅(h−2)2h⋅(h−1)(2)用(2) \text{(2)}(2)式减去(1) \text{(1)}(1)式T ( h ) 2 ⋅ T ( h ) − T ( h ) T(h) 2 \cdot T(h) - T(h)T(h)2⋅T(h)−T(h)T ( h ) − 2 1 ⋅ 1 ( 2 2 ⋅ 1 ) ( 2 3 ⋅ 1 ) ⋯ ( 2 h − 1 ⋅ 1 ) 2 h ⋅ ( h − 1 ) T(h) -2^1 \cdot 1 (2^2 \cdot 1) (2^3 \cdot 1) \dots (2^{h-1} \cdot 1) 2^h \cdot (h-1)T(h)−21⋅1(22⋅1)(23⋅1)⋯(2h−1⋅1)2h⋅(h−1)为了凑成完整的等比数列求和∑ i 0 h − 1 2 i 2 h − 1 \sum_{i0}^{h-1} 2^i 2^h - 1∑i0h−1​2i2h−1我们将2 0 1 2^01201加到等式两边T ( h ) − ( 2 0 2 1 2 2 ⋯ 2 h − 1 ) 2 h ⋅ ( h − 1 ) 2 0 T(h) -(2^0 2^1 2^2 \dots 2^{h-1}) 2^h \cdot (h-1) 2^0T(h)−(202122⋯2h−1)2h⋅(h−1)20T ( h ) − ∑ i 0 h − 1 2 i 2 h ⋅ ( h − 1 ) 1 T(h) -\sum_{i0}^{h-1} 2^i 2^h \cdot (h-1) 1T(h)−∑i0h−1​2i2h⋅(h−1)1T ( h ) − ( 2 h − 1 ) 2 h ⋅ ( h − 1 ) 1 T(h) -(2^h - 1) 2^h \cdot (h-1) 1T(h)−(2h−1)2h⋅(h−1)1T ( h ) − 2 h 1 h ⋅ 2 h − 2 h 1 T(h) -2^h 1 h \cdot 2^h - 2^h 1T(h)−2h1h⋅2h−2h1T ( h ) h ⋅ 2 h − 2 ⋅ 2 h 2 T(h) h \cdot 2^h - 2 \cdot 2^h 2T(h)h⋅2h−2⋅2h2T ( h ) 2 h ( h − 2 ) 2 T(h) 2^h (h - 2) 2T(h)2h(h−2)2将结点总数N 2 h − 1 N 2^h - 1N2h−1和高度h log ⁡ 2 ( N 1 ) h \log_2(N1)hlog2​(N1)代入得F ( N ) ( N 1 ) ( log ⁡ 2 ( N 1 ) − 2 ) 2 F(N) (N1)(\log_2(N1) - 2) 2F(N)(N1)(log2​(N1)−2)2因此向上调整算法的建堆时间复杂度为T A d j u s t U p _ B u i l d O ( N log ⁡ N ) T_{AdjustUp\_Build} O(N \log N)TAdjustUp_Build​O(NlogN)2. 向下调整AdjustDown的建堆时间复杂度O ( N ) O(N)O(N)向下调整操作通常用于删除堆顶元素用堆尾元素替换堆顶后或在建堆过程中用于将一个不符合堆性质的子树调整为堆。操作从父节点开始与其左右孩子节点中满足条件的那个孩子进行比较如果不满足堆性质则交换并向下递归直到满足堆性质或到达叶子节点。操作过程分析确定孩子确定左右孩子中较小的那个孩子child。比较与交换比较a[child]和a[parent]。若a[child] a[parent]则执行一次交换操作。移动交换后parent变为原来的childchild重新计算为新的parent * 2 1。在每一次循环中元素至多向下移动一层即操作次数 ≤ 1 \text{操作次数} \le 1操作次数≤1移动距离 1 层 \text{移动距离} 1 \text{ 层}移动距离1层该过程从根节点第 1 层开始一直向下追溯到叶子节点最深层H HH。最坏情况是元素从根节点一直向下移动到最底层路径长度恰好等于堆的高度H HH。该方法从最后一个非叶子结点开始依次对所有非叶子结点执行一次向下调整操作。推导过程同样以h hh层满二叉树为例。若规定根结点层数为 1则第i ii层的结点数n i 2 i − 1 n_i 2^{i-1}ni​2i−1该层结点向下调整的最大移动层数为h − i h-ih−i。总移动步数T ( h ) T(h)T(h)是每层结点数与其最大向下调整次数的乘积之和T ( h ) ∑ i 1 h − 1 2 i − 1 ⋅ ( h − i ) T(h) \sum_{i1}^{h-1} 2^{i-1} \cdot (h-i)T(h)i1∑h−1​2i−1⋅(h−i)展开求和项并令j i − 1 j i-1ji−1:T ( h ) ∑ j 1 h − 1 2 j ⋅ ( h − 1 − j ) 2 0 ⋅ ( h − 1 ) 2 1 ⋅ ( h − 2 ) 2 2 ⋅ ( h − 3 ) 2 3 ⋅ ( h − 4 ) ⋯ 2 h − 3 ⋅ 2 2 h − 2 ⋅ 1 ( 1 ) T(h) \sum_{j1}^{h-1} 2^j \cdot (h-1-j) 2^0\cdot(h-1) 2^1\cdot(h-2) 2^2\cdot(h-3) 2^3\cdot(h-4) \dots 2^{h-3}\cdot22^{h-2}\cdot1 \quad (\text{1})T(h)j1∑h−1​2j⋅(h−1−j)20⋅(h−1)21⋅(h−2)22⋅(h−3)23⋅(h−4)⋯2h−3⋅22h−2⋅1(1)使用错位相减法。将(1) \text{(1)}(1)式乘以公比r 2 r2r22 ⋅ T ( h ) 2 1 ⋅ ( h − 1 ) 2 2 ⋅ ( h − 2 ) 2 3 ⋅ ( h − 3 ) 2 4 ⋅ ( h − 4 ) ⋯ 2 h − 2 ⋅ 2 2 h − 1 ⋅ 1 ( 2 ) 2 \cdot T(h) 2^1\cdot(h-1) 2^2\cdot(h-2) 2^3\cdot(h-3) 2^4\cdot(h-4) \dots 2^{h-2}\cdot22^{h-1}\cdot1 \quad (\text{2})2⋅T(h)21⋅(h−1)22⋅(h−2)23⋅(h−3)24⋅(h−4)⋯2h−2⋅22h−1⋅1(2)用(2) \text{(2)}(2)式减去(1) \text{(1)}(1)式T ( h ) 2 ⋅ T ( h ) − T ( h ) T(h) 2 \cdot T(h) - T(h)T(h)2⋅T(h)−T(h)T ( h ) − 2 0 ( h − 1 ) 2 1 2 2 2 3 2 4 ⋯ 2 h − 2 2 h − 1 T(h) -2^0(h-1) 2^1 2^2 2^3 2^4 \dots 2^{h-2} 2^{h-1}T(h)−20(h−1)21222324⋯2h−22h−1为了凑成完整的等比数列∑ i 0 h − 1 2 i 2 h − 1 \sum_{i0}^{h-1} 2^i 2^h - 1∑i0h−1​2i2h−1我们将2 0 1 2^01201加到第一部分并进行整理T ( h ) 2 0 2 1 2 2 ⋯ 2 h − 1 − h T(h) 2^0 2^1 2^2 \dots 2^{h-1} - hT(h)202122⋯2h−1−hT ( h ) ∑ i 0 h − 1 2 i − h T(h) \sum_{i0}^{h-1} 2^i - hT(h)∑i0h−1​2i−hT ( h ) ( 2 h − 1 ) − h T(h) (2^h - 1) - hT(h)(2h−1)−h将结点总数N 2 h − 1 N 2^h - 1N2h−1和高度h log ⁡ 2 ( N 1 ) h \log_2(N1)hlog2​(N1)代入T ( N ) N − log ⁡ 2 ( N 1 ) T(N) N - \log_2(N1)T(N)N−log2​(N1)由于N NN远大于log ⁡ 2 ( N 1 ) \log_2(N1)log2​(N1)因此该建堆方法的时间复杂度为T A d j u s t D o w n _ B u i l d O ( N ) T_{AdjustDown\_Build} O(N)TAdjustDown_Build​O(N)II. Top-K 问题TOP-K问题即从N NN个数据中找出前K KK个最⼤的元素或者最⼩的元素⼀般情况下数据量都⽐较⼤。⽐如专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。对于Top-K问题能想到的最简单直接的⽅式就是排序但是如果数据量⾮常⼤排序就不太可取了(可能数据都不能⼀下⼦全部加载到内存中)。最佳的⽅式就是⽤堆来解决基本思路如下⽤数据集合中前K个元素来建堆前K KK个最⼤的元素则建小堆。前K KK个最⼩的元素则建大堆。⽤剩余的N − K N-KN−K个元素依次与堆顶元素来⽐较不满⾜则替换堆顶元素。将剩余N − K N-KN−K个元素依次与堆顶元素⽐完之后堆中剩余的K KK个元素就是所求的前K KK个最小或者最大的元素。1. 核心策略为了高效地找出前K KK个最大的元素我们维护一个大小为K KK的小顶堆Min-Heap。为什么选择小顶堆小顶堆的堆顶元素是这K KK个数中的最小值。我们想要找到的是最大的K KK个数。当遍历到一个新的数X XX时如果X XX比堆顶的最小值还要大说明X XX有资格成为前K KK大的数之一。此时我们用X XX替换掉堆顶的最小值然后对堆进行向下调整确保堆中仍然是当前遍历到的所有数中的最大K KK个数。具体步骤阶段一读取数据流中的前K KK个数并用这K KK个数建立一个大小为K KK的小顶堆使用向下调整算法时间复杂度为O ( N ) O(N)O(N)。// 阶段一读取文件中前k个数并建堆for(inti0;ik;i){fscanf(fout,%d,kminheap[i]);}// 建立K个数的小顶堆// 从最后一个非叶子节点开始向下调整for(inti(k-1-1)/2;i0;i--){AdjustDown(kminheap,k,i);}阶段二遍历与调整从第K 1 K1K1个数开始依次读取剩下的N − K N-KN−K个数X XX。判断如果X 堆顶元素 X \text{堆顶元素}X堆顶元素即X XX大于当前已知的K KK个最大数中的最小值则执行替换。替换与调整将堆顶元素替换为X XX然后对新的堆顶执行向下调整AdjustDown操作以恢复小顶堆的性质。向下调整的时间复杂度O ( log ⁡ K ) O(\log K)O(logK)。// 阶段二读取剩下的N-K个数并调整堆intx0;while(fscanf(fout,%d,x)0){// 核心判断如果新读取的数比堆顶K个数中的最小值大if(xkminheap[0]){// 替换堆顶kminheap[0]x;// 向下调整恢复小顶堆性质AdjustDown(kminheap,k,0);}}阶段三遍历结束后堆中剩下的K KK个元素即为原数据流中最大的K KK个数。// 阶段三输出结果printf(最大前%d个数,k);for(inti0;ik;i){printf(%d ,kminheap[i]);}printf(\n);2.Top-K 问题的时间复杂度分析假设数据流中的总数据量为N NN我们需要找出最大的K KK个数。阶段一建堆读取前K KK个数O ( K ) O(K)O(K)建立大小为K KK的小顶堆通过O ( K ) O(K)O(K)次AdjustDown操作O ( K ) O(K)O(K)总时间T I n i t O ( K ) T_{Init} O(K)TInit​O(K)阶段二遍历与调整需要处理N − K N-KN−K个数。对于每个数X XX判断是否大于堆顶O ( 1 ) O(1)O(1)。如果需要替换则执行一次向下调整AdjustDown操作。AdjustDown操作在大小为K KK的堆上时间复杂度为O ( log ⁡ K ) O(\log K)O(logK)。总时间T L o o p ( N − K ) × O ( log ⁡ K ) O ( ( N − K ) log ⁡ K ) T_{Loop} (N-K) \times O(\log K) O((N-K) \log K)TLoop​(N−K)×O(logK)O((N−K)logK)最终时间复杂度T T o t a l T I n i t T L o o p O ( K ) O ( ( N − K ) log ⁡ K ) T_{Total} T_{Init} T_{Loop} O(K) O((N-K) \log K)TTotal​TInit​TLoop​O(K)O((N−K)logK)由于N NN往往远大于K KK所以N − K ≈ N N-K \approx NN−K≈N。T T o p K ≈ O ( N log ⁡ K ) T_{TopK} \approx O(N \log K)TTopK​≈O(NlogK)优势分析相比于直接对所有N NN个元素进行排序时间复杂度O ( N log ⁡ N ) O(N \log N)O(NlogN)堆方法的时间复杂度O ( N log ⁡ K ) O(N \log K)O(NlogK)要高效得多尤其当K ≪ N K \ll NK≪N时。例如在一个包含十亿1 0 9 10^9109个数据的集合中找前 100 个最大的数O ( N log ⁡ N ) ≈ 1 0 9 × log ⁡ 2 ( 1 0 9 ) ≈ 1 0 9 × 30 O(N \log N) \approx 10^9 \times \log_2(10^9) \approx 10^9 \times 30O(NlogN)≈109×log2​(109)≈109×30O ( N log ⁡ K ) ≈ 1 0 9 × log ⁡ 2 ( 100 ) ≈ 1 0 9 × 6.6 O(N \log K) \approx 10^9 \times \log_2(100) \approx 10^9 \times 6.6O(NlogK)≈109×log2​(100)≈109×6.6可见使用堆解决 Top-K 问题的效率提升是巨大的这使得该算法成为处理大数据集中 Top-K 问题的首选方法。III. 总结本文对堆排序的核心调整操作进行了严格的时间复杂度分析向上调整建堆AdjustUp最坏时间复杂度为O ( N log ⁡ N ) O(N \log N)O(NlogN)。向下调整建堆AdjustDown最坏时间复杂度为O ( N ) O(N)O(N)。建堆操作Build Heap通过N NN次O ( log ⁡ N ) O(\log N)O(logN)的向下调整的求和分析证明其总时间复杂度为线性的O ( N ) O(N)O(N)。在此基础上我们利用堆的特性实现了 Top-K 问题的最优解法。通过维护一个大小为K KK的小顶堆算法避免了对全数据集的完全排序将时间复杂度优化至O ( N log ⁡ K ) O(N \log K)O(NlogK)使其成为处理大规模数据集中 Top-K 问题的最有效策略之一。