在一个 最小堆 (min heap) 中，如果 P 是 C 的一个父级节点，那么 P 的 key（或 value) 应小于或等于 C 的对应值。 正因为此，堆顶元素一定是最小的，我们会利用这个特点求最小值或者第 k 小的值。
在一个 最大堆 (max heap) 中，P 的 key（或 value) 大于或等于 C 的对应值。
以python为例，说明堆的几个常见操作，这里需要用到一个内置的包：heapq
python中使用堆是通过传入一个数组，然后调用一个函数，在原地让传入的数据具备堆的特性
需要注意的是，heapify默认构造的是小顶堆（min heap），如果要构造大顶堆，思路是把所有的数值倒转，既* -1，例如：
使用heapq提供的函数： heappop 来实现
具体使用方式参考 初始化Heapify
使用heapq提供的函数： heappush 来实现
同时heapq还提供另外一个函数： heappushpop ，能够在一个函数实现push&pop两个操作；顺序是：先push再pop
根据官方文档的描述，这个函数会比先在外围先调用heappush，再调用heappop，效率更高
先pop数据再push数据，和heappushpop的顺序是反着的； 同样的，这样调用的性能也会比先调用heappop再调用heappush更好
如果pop的时候队列是空的，会抛出一个异常
可以通过 heapq.merge 将多个 已排序 的输入合并为一个已排序的输出，这个本质上不是堆；其实就是用两个指针迭代
对于这个问题，有一个算法题可以实现相同的功能
从 iterable 所定义的数据集中返回前 n 个最大/小元素组成的列表。
函数为： heapq.nlargest() | heapq.nsmallest()
heapq - Heap queue algorithm - Python 3.10.4 documentation
某个时间段内，数据涌来，这就是并发。如果数据量很大，就是高并发
高并发的解决方法：
1、队列、缓冲区
假设只有一个窗口，陆续涌入食堂的人，排队打菜是比较好的方式
所以，排队（队列）是一种天然解决并发的办法
排队就是把人排成 队列，先进先出，解决了资源使用的问题
排成的队列，其实就是一个缓冲地带，就是 缓冲区
假设女生优先，每次都从这个队伍中优先选出女生出来先打饭，这就是 优先队列
例如queue模块的类Queue、LifoQueue、PriorityQueue（小顶堆实现）
2、争抢
只开一个窗口，有可能没有秩序，也就是谁挤进去就给谁打饭
挤到窗口的人占据窗口，直到打到饭菜离开
其他人继续争抢，会有一个人占据着窗口，可以视为锁定窗口，窗口就不能为其他人提供服务了。
这是一种锁机制
谁抢到资源就上锁，排他性的锁，其他人只能等候
争抢也是一种高并发解决方案，但是，这样可能不好，因为有可能有人很长时间抢不到
3、预处理
如果排长队的原因，是由于每个人打菜等候时间长，因为要吃的菜没有，需要现做，没打着饭不走开，锁定着窗口
食堂可以提前统计大多数人最爱吃的菜品，将最爱吃的80%的热门菜，提前做好，保证供应，20%的冷门菜，现做
这样大多数人，就算锁定窗口，也很快打到饭菜走了，快速释放窗口
一种提前加载用户需要的数据的思路，预处理 思想，缓存常用
更多Python知识，请关注：Python自学网！！
.example-btn{color:#fffbackground-color:#5cb85cborder-color:#4cae4c}.example-btn:hover{color:#fffbackground-color:#47a447border-color:#398439}.example-btn:active{background-image:none}div.example{width:98%color:#000background-color:#f6f4f0background-color:#d0e69cbackground-color:#dcecb5background-color:#e5eeccmargin:0 0 5px 0padding:5pxborder:1px solid #d4d4d4background-image:-webkit-linear-gradient(#fff,#e5eecc 100px)background-image:linear-gradient(#fff,#e5eecc 100px)}div.example_code{line-height:1.4emwidth:98%background-color:#fffpadding:5pxborder:1px solid #d4d4d4font-size:110%font-family:Menlo,Monaco,Consolas,"Andale Mono","lucida console","Courier New",monospaceword-break:break-allword-wrap:break-word}div.example_result{background-color:#fffpadding:4pxborder:1px solid #d4d4d4width:98%}div.code{width:98%border:1px solid #d4d4d4background-color:#f6f4f0color:#444padding:5pxmargin:0}div.code div{font-size:110%}div.code div,div.code p,div.example_code p{font-family:"courier new"}pre{margin:15px autofont:12px/20px Menlo,Monaco,Consolas,"Andale Mono","lucida console","Courier New",monospacewhite-space:pre-wrapword-break:break-allword-wrap:break-wordborder:1px solid #dddborder-left-width:4pxpadding:10px 15px} 排序算法是《数据结构与算法》中最基本的算法之一。排序算法可以分为内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。以下是堆排序算法：
堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：
大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列； 小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；
堆排序的平均时间复杂度为 Ο(nlogn)。
1. 算法步骤
创建一个堆 H[0……n-1]；
把堆首（最大值）和堆尾互换；
把堆的尺寸缩小 1，并调用 shift_down(0)，目的是把新的数组顶端数据调整到相应位置；
重复步骤 2，直到堆的尺寸为 1。
2. 动图演示
代码实现 JavaScript实例var len // 因为声明的多个函数都需要数据长度，所以把len设置成为全局变量
function buildMaxHeap ( arr ) { // 建立大顶堆
len = arr. length
for ( var i = Math . floor ( len / 2 ) i >= 0 i -- ) {
heapify ( arr , i )
}
}
function heapify ( arr , i ) { // 堆调整
var left = 2 * i + 1 ,
right = 2 * i + 2 ,
largest = i
if ( leftarr [ largest ] ) {
largest = left
}
if ( rightarr [ largest ] ) {
largest = right
}
if ( largest != i ) {
swap ( arr , i , largest )
heapify ( arr , largest )
}
}
function swap ( arr , i , j ) {
var temp = arr [ i ]
arr [ i ] = arr [ j ]
arr [ j ] = temp
}
function heapSort ( arr ) {
buildMaxHeap ( arr )
for ( var i = arr. length - 1 i > 0 i -- ) {
swap ( arr , 0 , i )
len --
heapify ( arr , 0 )
}
return arr
}
Python 实例def buildMaxHeap ( arr ) :
import math
for i in range ( math . floor ( len ( arr ) / 2 ) , - 1 , - 1 ) :
heapify ( arr , i )
def heapify ( arr , i ) :
left = 2 *i+ 1
right = 2 *i+ 2
largest = i
if leftarr [ largest ] :
largest = left
if rightarr [ largest ] :
largest = right
if largest != i:
swap ( arr , i , largest )
heapify ( arr , largest )
def swap ( arr , i , j ) :
arr [ i ] , arr [ j ] = arr [ j ] , arr [ i ]
def heapSort ( arr ) :
global arrLen
arrLen = len ( arr )
buildMaxHeap ( arr )
for i in range ( len ( arr ) - 1 , 0 , - 1 ) :
swap ( arr , 0 , i )
arrLen - = 1
heapify ( arr , 0 )
return arr
Go 实例func heapSort ( arr [] int ) [] int {
arrLen := len ( arr )
buildMaxHeap ( arr , arrLen )
for i := arrLen - 1i >= 0i -- {
swap ( arr , 0 , i )
arrLen -= 1
heapify ( arr , 0 , arrLen )
}
return arr
}
func buildMaxHeap ( arr [] int , arrLen int ) {
for i := arrLen / 2i >= 0i -- {
heapify ( arr , i , arrLen )
}
}
func heapify ( arr [] int , i , arrLen int ) {
left := 2 * i + 1
right := 2 * i + 2
largest := i
if left arrLen &&arr [ left ] >arr [ largest ] {
largest = left
}
if right arrLen &&arr [ right ] >arr [ largest ] {
largest = right
}
if largest != i {
swap ( arr , i , largest )
heapify ( arr , largest , arrLen )
}
}
func swap ( arr [] int , i , j int ) {
arr [ i ], arr [ j ] = arr [ j ], arr [ i ]
}
Java 实例public class HeapSort implements IArraySort {
@Override
public int [ ] sort ( int [ ] sourceArray ) throws Exception {
// 对 arr 进行拷贝，不改变参数内容
int [ ] arr = Arrays . copyOf ( sourceArray, sourceArray. length )
int len = arr. length
buildMaxHeap ( arr, len )
for ( int i = len - 1 i > 0 i -- ) {
swap ( arr, 0 , i )
len --
heapify ( arr, 0 , len )
}
return arr
}
private void buildMaxHeap ( int [ ] arr, int len ) {
for ( int i = ( int ) Math . floor ( len / 2 ) i >= 0 i -- ) {
heapify ( arr, i, len )
}
}
private void heapify ( int [ ] arr, int i, int len ) {
int left = 2 * i + 1
int right = 2 * i + 2
int largest = i
if ( leftarr [ largest ] ) {
largest = left
}
if ( rightarr [ largest ] ) {
largest = right
}
if ( largest != i ) {
swap ( arr, i, largest )
heapify ( arr, largest, len )
}
}
private void swap ( int [ ] arr, int i, int j ) {
int temp = arr [ i ]
arr [ i ] = arr [ j ]
arr [ j ] = temp
}
}
PHP实例function buildMaxHeap ( & $arr )
{
global $len
for ( $i = floor ( $len / 2 )$i >= 0$i -- ) {
heapify ( $arr , $i )
}
}
function heapify ( & $arr , $i )
{
global $len
$left = 2 * $i + 1
$right = 2 * $i + 2
$largest = $i
if ( $left $arr [ $largest ] ) {
$largest = $left
}
if ( $right $arr [ $largest ] ) {
$largest = $right
}
if ( $largest != $i ) {
swap ( $arr , $i , $largest )
heapify ( $arr , $largest )
}
}
function swap ( & $arr , $i , $j )
{
$temp = $arr [ $i ]
$arr [ $i ] = $arr [ $j ]
$arr [ $j ] = $temp
}
function heapSort ( $arr ) {
global $len
$len = count ( $arr )
buildMaxHeap ( $arr )
for ( $i = count ( $arr ) - 1$i > 0$i -- ) {
swap ( $arr , 0 , $i )
$len --
heapify ( $arr , 0 )
}
return $arr
}
C 实例#include
#include
void swap ( int * a , int * b ) {
int temp = * b
* b = * a
* a = temp
}
void max_heapify ( int arr [ ] , int start , int end ) {
// 建立父节点指标和子节点指标
int dad = start
int son = dad * 2 + 1
while ( son 0 i -- ) {
swap ( &arr [ 0 ] , &arr [ i ] )
max_heapify ( arr , 0 , i - 1 )
}
}
int main ( ) {
int arr [ ] = { 3 , 5 , 3 , 0 , 8 , 6 , 1 , 5 , 8 , 6 , 2 , 4 , 9 , 4 , 7 , 0 , 1 , 8 , 9 , 7 , 3 , 1 , 2 , 5 , 9 , 7 , 4 , 0 , 2 , 6 }
int len = ( int ) sizeof ( arr ) / sizeof ( * arr )
heap_sort ( arr , len )
int i
for ( i = 0 i
