创建堆的方式有两种，一种是一边插入结点，一边调用堆的插入方法调整堆，这样的时间复杂度就是

O(NlogN)，而第二种方式就把时间复杂度缩减到了O(N)，它是采用先把结点插入好了，然后再来调整堆，并不是一边插入一边调整。

但是从代码层面来看，可能会误以为第二种方式的时间复杂度也是O(NlogN)，但第二种方式是从下往上建立堆。举个例子，如下所示，假设堆中存在了N个节点(满足堆的性质)，采用第一种方式，再创建N个结点，那么插入第一个数时，就调用了时间复杂度为logN的插入方法，插入N个数后，时间复杂度为logN。


让我们看看第二种方式会如何？

先把N个结点创建到树中，把这N个结点具体化，我们看到在调整树时，第一次是以倒数第二层的结点作为根节点，然后来调整这棵子树，也就是它的时间复杂度不再是logN了，因为远远没到N个结点，远远没到整颗树的高度，它的时间复杂度应该如下判断，在最坏情况下，树中每个结点，会一直向下查找，一直到底，假设树高为h,则倒数第二层会向下查找1次，倒数第三层会向下查找2次…

倒数第二层结点数为2(h-2),倒数第三层2h-3…




JAVA代码实现
import java.util.ArrayList;
import java.util.Arrays;

//必须传入一个Comparable的实现类，因为后续会用到类的内部比较器
public class Heap<E extends Comparable> {
    Comparable<? super E>[] list;//堆--存储Comparable的实现类
    int size;  //堆长度
    int capacity;//堆容量

    public Heap(int capacity){
        this.capacity=capacity;
        size=0;
        list=new Comparable[capacity+1];
    }

    //初始化
    public void Init(E value,int index){
        if(index>0)
        { list[index]= value;
          size++;
        }
        else
            new RuntimeException("下标越界");
    }

    //创建堆
    public void Build_Max_Heap(){
       for(int i=size/2;i>0;i--){
           int child=0;
           int parent = i;
           Comparable par_X= (E) list[i];
           for(;parent*2 <= size;parent=child){
               child=parent*2;
               if(child+1<=size && list[child].compareTo((E) list[child+1]) ==-1)
                   child++;
               if(par_X.compareTo((E) list[child])==1)
                   break;
               list[parent]=list[child];
           }
           list[parent]=(E) par_X;
       }
    }

    //插入堆
   public void Insert(E node){
        list[++size]=node;
        for(int i=size;i/2>=0;i=i/2){
            if(i==1 || list[i/2].compareTo((E)node)==1){
                 list[i]=node;
                 break;
            }
            else{
                list[i]=list[i/2];
           }
        }
   }

   //删除堆
   public E Delete(){
        Comparable DeleteX=list[1];
        Comparable X=list[size--];
        int child=1;
        int parent=1;
        for(;parent*2<=size;parent=child){
            child=parent*2;
            if(child+1<=size && list[child].compareTo((E)list[child+1])==-1 )
                child++;
            if(X.compareTo((E)list[child])==-1)
                list[parent]=list[child];
            else
                break;
        }
        list[parent]=X;
        return (E)DeleteX;
   }

    //测试数据
    public static void main(String[] args) {
        Heap<SSS> heap = new Heap<>(10);
        heap.Init(new SSS(1),1);
        heap.Init(new SSS(2),2);
        heap.Init(new SSS(3),3);
        heap.Init(new SSS(4),4);
        heap.Init(new SSS(5),5);
        heap.Insert(new SSS(6));
        heap.Build_Max_Heap();
        heap.Delete();
        for(int i=1;i<=heap.size;i++)
            System.out.println(heap.list[i]);
    }
}
class SSS implements Comparable {
   int X;

    @Override
    public int compareTo(Object o) {
        SSS s2=(SSS) o;
        if(X>s2.X)
            return 1;
        if(X<s2.X)
            return -1;
        else return 0;
    }
    public SSS(int X){
        this.X=X;
    }

    @Override
    public String toString() {
        return "SSS{" +
                "X=" + X +
                '}';
    }
}

堆排序思想：
堆排序，利用堆这种数据结构设计的一种排序算法，是选择排序的一种。
堆是一种近似完全二叉树的数据结构，并且：子节点的键值或索引总是小于（或者大于）它的父节点。
算法描述：
构造初始堆。将给定无序序列构造成一个堆（一般升序采用大顶堆，降序采用小顶堆)；
将堆顶元素与末尾元素进行交换，使末尾元素最大/最小，则末尾就是排好序的数组。
然后继续调整堆为大顶堆/小顶堆。
再将堆顶元素与末尾元素交换，得到第二大元素；
重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素；
如此反复进行交换、重建、交换，直到整个序列有序。
参考：
https://zhuanlan.zhihu.com/p/73714165
https://zhuanlan.zhihu.com/p/142673431
南风以南：python实现·十大排序算法之堆排序(Heap Sort)
我的理解之大白话：
好不容易看懂了，咱必须得唠唠，（害，写的啥玩意，感觉语句不通的）：
首先，堆，大顶堆，小顶堆的定义都很明显。下图里左右分别为大顶堆和小顶堆。
2. 我在思考的时候，就觉得有三个问题骚扰着我：
列表和树怎么建立关系？
emmm很简单，例如上面那个大顶堆，写成数组就是[9,5,8,2,3,4,7,1]
哈哈哈其实就是树的按行读取啦。
所以不要怀疑，[9,5,8,2,3,4,7,1]就是上面那棵树，上面那棵树就是[9,5,8,2,3,4,7,1]
对于待排序序列：[91, 60, 96, 13, 35, 65, 46, 65, 10, 30, 20, 31, 77, 81,22]，我们先给他画成树的形式。如下图，而我们的目标是把他转化为大顶堆。
我怎么把给序列的一般树排序成大顶堆呢？
这就是堆排序算法里的重点了，我们将问题拆解，根据堆关于父子节点数值问题的定义，其实这个树可以拆解为众多的 父节点和子节点 组，比如上图，基本单位就是[91,60,96] [60,13,35] [96,65,46], [13,65,10], [35,30,20], [65,31,77], [46,81,22]。我们只要保证这些基本单位都满足堆的定义，那么就肯定没得问题了。
那么问题来了，怎么确保单元内部满足堆的条件呢？
首先需要解决的就是，数组id和数据在树中的位置关系。在数组里，父节点和字节点怎么确定，那么通过找规律我们可以发现，父节点index是 n 的话，那么其左右节点就是 2n+1 , 2n+2。
那么基本单位的排序顺序怎么订？我们是从上而下调整基本单位？还是从下而上呢？答案是从下而上。有人回答啦，我觉得还挺在理：“堆是一个二叉树，以最大堆为例，建堆的本质是让这颗二叉树满足父节点的值大于等于子节点节点。自底向上本质上就是一个倒序的层次遍历，每个层上的元素与自己的孩子比较一下，保证自己大于子节点，最后堆顶一定是最大值。通过层层向上的方式，符合堆性质的区域从底层向上扩张，最终建堆完成。如果是自顶向下，当第i层和他的孩子i+1层比较中出现交换，交换后的i层不能保证小于i-1层，于是又要向上验证，最坏情况是验证到顶。”
链接在这：https://www.zhihu.com/question/65501536
然后既然是基本单元，就知道肯定存在迭代的啦。出现交换的话肯定要迭代进行判断交换后的是否依旧满足。这个代码中会体现。
排成这个样子之后我怎么取出来？
问题来了，我排成大顶堆，只能说最顶层的数值最大，其他还是不确定，也不能得到排序后的结果。
这就对了，我们排好大顶堆之后啊，其实只能拿到一个最大的值，咱们就默默的把他和数组最后一位 的数据进行交换，那么咱们的最后一位数字是不是就相当于排序好了呀。然后刚才本来的最后一位被放在根节点了，这又不是大顶堆了，我们就需要对这个交换后的树重新堆排序，再排个第二大的数据出来，当然这个去排序的树，肯定要砍掉刚才被放到最后一位的最大数了。
然后就是 拿出一位最大数，再堆排序，再拿，直到全部排完，我们就结束啦。
写了半天，咱也不知道自己写了个啥玩意。上代码吧还是您。
python代码实现：
def buildHeap(sortList,lenS,target):
    # 堆树的基本单元进行整理
    largest = target
    left,right = 2*target+1, 2*target+2
    # 如果是逆序排序，直接把下面两个if里面的大于号换成小于号，构建小顶堆就行了
    if left<lenS and sortList[left]>sortList[target]: largest = left
    if right<lenS and sortList[right]>sortList[largest]: largest = right
    if largest != target:
        sortList[largest],sortList[target] = sortList[target],sortList[largest]
        # 发生交换，则进行迭代整理
        buildHeap(sortList,lenS,largest)

def heapSort(sortList):
    lenS = len(sortList)
    # 最后一个父节点的id
    last_root = lenS//2-1
    # 自底向上构建堆
    for i in range(last_root,-1,-1):
        buildHeap(sortList, lenS, i)
    # 取出堆顶元素，进行排序
    for end in range(lenS-1, 0, -1):
        sortList[0], sortList[end] = sortList[end], sortList[0]
        # end每次都会减1，所以就自动排除后面已经排序好的数据了
        buildHeap(sortList, end, 0)
    return sortList

print(heapSort([1,9,8,6,9,2,9,5,4,3,8]))
时间复杂度： 
【好坏都是 
 】
空间复杂度： 
 【一直都在原址修改】
不稳定排序
ps：排序算法稳定性的判定
稳定：如果 
 原本在 
 前面，而 
 ，排序之后 
 仍然在 
 的前面。
不稳定：如果 
 原本在 
 的前面，而 
 ，排序之后 
 可能会出现在 
 的后面。
至于时间复杂度怎么算的：放过我吧老天爷啊啊啊啊啊

原文地址为：堆排序 两种实现（最小堆和最大堆）

 
 
堆排序算法是建立在二叉树的堆结构上的，通过交换堆（一维数组）中的元素，并进行上浮或下沉函数运算实现多次调整
 
堆排序算法的复杂度低，和快速排序属于相同速度级别的一种快速的排序算法
 
下面以最小堆和最大堆来进行堆排序算法的实现，具体内容在代码中进行讲解
 


 
1.最小堆 堆排序
 
#include"iostream"
#include"cstdio"


using namespace std;


int h[100];               //堆
int n;
int num;            //num的意义在于，在n的值不断减小的时候，保存n原来的值，以便我们在最后输出排序后的数组的时候，丢失原来的数组元素个数的值


void swap(int x,int y)                       //必要的交换函数
{
int t;
t=h[x];
h[x]=h[y];
h[y]=t;
}


void siftdown(int i)                          //子树的向下调整，构建局部最小堆
{
int t,flag=0;
while(i*2<=n&&flag==0)
{
if(h[i]>h[i*2])
{
t=2*i;
}
else
{
t=i;
}
if(i*2+1<=n)
{
if(h[t]>h[2*i+1])
{
t=2*i+1;
}
}
if(t!=i)
{
swap(t,i);
i=t;
}
else
{
flag=1;
}
} 
}


/*void siftup(int i)
{
int flag=0;
if(i==1)
{
return ;
}
else
{
while(i!=1&&flag==0)
{
if(h[i]<h[i/2])
{
swap(i,i/2);
i=i/2;
}
else
{
flag=1;
}
}
}
}*/


int delet()                             //每次返回对顶元素，堆顶元素出堆的顺序是排序好的
{
int t;
t=h[1];
h[1]=h[n];                   //交换的目的是和下面的n--和siftdown共同保证每次出堆的是标准的要求的顺序
n--;
siftdown(1);
return t;
}


int main()
{
cin>>n;
num=n;
for(int i=1;i<=n;i++)
{
scanf("%d",&h[i]);
}
for(int i=n/2;i>=1;i--)
{
siftdown(i);
}
for(int i=1;i<=num;i++)
{
printf("%d ",delet());
}
return 0;
} 

 


 


 
2.最大堆  堆排序
 


 
#include"iostream"
#include"cstdio"


using namespace std;


int h[100];
int n;
int num;


void swap(int x,int y)
{
int t;
t=h[x];
h[x]=h[y];
h[y]=t;
}

  
void siftdown(int i)                            //构建最大数的siftdown下沉函数
{
int t,flag=0;
while(i*2<=n&&flag==0)
{
if(h[i]<h[i*2])
{
t=2*i;
}
else
{
t=i;
}
if(i*2+1<=n)
{
if(h[t]<h[i*2+1])
{
t=2*i+1;
}
}
if(t!=i)
{
swap(t,i);
i=t;
} 
else
{
flag=1;
}
}
}


void heapsort()                        //heapsort堆排序函数
{
while(n>1)
{
swap(1,n);
n--;                                           //这三句的目的是将最大的元素不断从堆顶有序的排列到堆尾，以便最后进行整体输出
siftdown(1);
}
}


int main()
{
cin>>n;
num=n;
for(int i=1;i<=n;i++)
{
scanf("%d",&h[i]);
}
for(int i=n/2;i>=1;i--)
{
siftdown(i);
}
heapsort();
for(int i=1;i<=num;i++)
{
printf("%d ",h[i]);
}
return 0;
}
 

转载请注明本文地址：堆排序 两种实现（最小堆和最大堆）

以下是最小堆添加节点和删除最小节点的功能实现。

特点：
A.完全二叉树（降低高度）。
B.充分利用数组存储，通过下标可以直接找到父子关系。
C.插入新元素和/删除最小元素不需要大量移动，最坏只需要进行logN次重新调整即可。
D.获取最小值时间复杂度O(1)。
E.操作过程适合实现优先队列。
F.堆排序时间复杂度O(NlogN)。


class Heap
{
public:
    typedef int key_t;
    Heap(size_t max = 64);
    ~Heap();

    key_t GetMin();
    bool Add(key_t key);
    bool RemoveMin();
    
private:
    size_t _max;
    size_t _count;
    key_t *_nodes;
};


Heap::Heap(size_t max) : _max(max),_count(0),_nodes(NULL)
{
    if (_max)
        _nodes = new key_t[_max+1];
}

Heap::~Heap()
{
    if (_nodes)
        delete []_nodes;
}

Heap::key_t Heap::GetMin()
{
    return _count > 0 ? _nodes[1] : numeric_limits<int>::min();
}

bool Heap::Add(key_t key)
{
    int curIndex;
    
    if (_count < _max) {
        _nodes[++_count] = key;
        curIndex = _count;

        while(curIndex > 1) {
            if(_nodes[curIndex] < _nodes[curIndex/2]) {
                key_t tmp = _nodes[curIndex/2];
                _nodes[curIndex/2] = _nodes[curIndex];
                _nodes[curIndex] = tmp;
                curIndex /= 2;
            } else {
                return true;
            }
        }
    } else {
        cout<<"===>Can't be inserted, limit to maxmium!"<<endl;
        return false;
    }
    return true;
}

bool Heap::RemoveMin()
{
    if (_count) {
        size_t curIndex = 1, min;
        _nodes[1] = _nodes[_count--];
        while(2*curIndex <= _count) {
            min = 2*curIndex;
            if (2*curIndex+1 <= _count) {
                min = _nodes[2*curIndex] < _nodes[2*curIndex+1] ? 2*curIndex : 2*curIndex+1;
            } 

            if (_nodes[curIndex] > _nodes[min]) {
                key_t tmp = _nodes[curIndex];
                _nodes[curIndex] = _nodes[min];
                _nodes[min] = tmp;
                curIndex = min;
            } else {
                return true;
            }
        }

        return true;
    }

    cout<<"===>Can't be removed, heap is already empty!"<<endl;
    return false;
}