以下是使用筛选法建立最小堆的代码，用于建堆的数据为{35,26,48,10,59,64,17,23,45,31}。
筛选法也即，从堆的最右下一个分支节点起，自下而上遍历每一个分支节点，使得以该分支节点为根的子树成为最小堆。

//筛选法+建立最小堆
#include<iostream>
using namespace std;

//类型定义与变量说明
const int DefaultSize=100;
typedef int datatype;
typedef struct
{
    datatype key;//关键字
    //......其他属性字段
}node;
typedef struct
{
    node *Heap;
    int CurrentSize;
    int MaxHeapSize;
}minHeap;
minHeap mh;
int start,EndOfHeap;

//筛选法
void FilterDown(minHeap &mh,int start,int EndOfHeap)
{
    int i=start,j=2*i+1;
    node temp=mh.Heap[i];
    while(j<=EndOfHeap)
    {
        if(j<EndOfHeap&&mh.Heap[j].key>mh.Heap[j+1].key)
            j++;
        if(temp.key<=mh.Heap[j].key)
            break;
        else
        {
            mh.Heap[i]=mh.Heap[j];
            i=j;
            j=2*j+1;
        }
        mh.Heap[i]=temp;
    }
}

//建立最小堆
void MinHeap(minHeap &mh,node A[],int n)
{
    int i,CurrentPos;
    mh.MaxHeapSize=DefaultSize<n?n:DefaultSize;
    mh.Heap=new node[mh.MaxHeapSize];
    if(mh.Heap==NULL)
    {
        cout<<"Memory Allocation Error1"<<endl;
        return;
    }
    for(i=0;i<n;i++)
        mh.Heap[i]=A[i];
    mh.CurrentSize=n;
    CurrentPos=(mh.CurrentSize-2)/2;
    while(CurrentPos>=0)
    {
        FilterDown(mh,CurrentPos,mh.CurrentSize-1);
        CurrentPos--;
    }
}

//测试方法
int main()
{
    node A[10]={35,26,48,10,59,64,17,23,45,31};
    MinHeap(mh,A,10);
    for(int i=0;i<10;i++)
        cout<<mh.Heap[i].key<<" ";
    cout<<endl;
    return 0;
}

最小堆的定义

最小堆是一颗完全二叉树，他的每一个节点的值不大于其左右子节点的值。

利用数组建立最小堆

leaf_name=['A','B','C','D','E','F','G','H'];
leaf_data=[10,1,1,11,1,1,8,5];
my_heap=heap();
my_heap.min_heap_create(leaf_name,leaf_data);

函数定义如下：
     function heap = heap()
            heap.size=0;
            heap.name=[];
            heap.data=[];
     end

     function min_heap_create(heap,name,data)
          N=length(name);
          for n=1:N
              heap.name(n)=name(n);
              heap.data(n)=data(n);
              heap.size=heap.size +1;
          end
      end

运行结果如下：
node 1–>A–>10
node 2–>B–>1
node 3–>C–>1
node 4–>D–>11
node 5–>E–>1
node 6–>F–>1
node 7–>G–>8
node 8–>H–>5
图状表示如下：

节点下沉算法

因为最小堆的子树也是最小堆，所以可以从底部开始建立，采用节点下沉算法。如果子节点的值比本身小，将左右子节点中最小的一个和本身交换，相等的情况下左子节点优先交换。逐步下降，直到本身的节点不大于子节点停止。代码如下：

       function heap_down_sink(heap,self)  
           lchild =self*2;
           rchild =self*2+1;
           if(lchild <= heap.size && rchild <= heap.size) 
              if(heap.data(self) > heap.data(lchild) || heap.data(self) > heap.data(rchild))                   
                  if(heap.data(lchild) <= heap.data(rchild))%左右子树相等的情况下，优先往左子树下沉           
                       heap_swap_node(heap,lchild,self);
                       heap_down_sink(heap,lchild);
                  else     
                       heap_swap_node(heap,rchild,self);
                       heap_down_sink(heap,rchild);
                  end
              end
           elseif(lchild <= heap.size)%仅仅只存在左叶子树
              if(heap.data(self) > heap.data(lchild))                    
                   heap_swap_node(heap,lchild,self);    
              end
           end
       end

利用上面的节点下降算法调整二叉堆，使之满足最小堆的特性。方法是从最后一个节点开始，逐个运行节点下沉算法，就可以实现要求。函数如下：

function   min_heap_adjust(heap)                   
    n=heap.size;
    while(n>=1)
        heap_down_sink(heap,n)
        n=n-1;
    end                
end

运行结果如下：
node 1–>B–>1
node 2–>E–>1
node 3–>C–>1
node 4–>H–>5
node 5–>A–>10
node 6–>F–>1
node 7–>G–>8
node 8–>D–>11
图状表示如下：

往最小堆中插入节点

插入节点不能破坏堆的特性，因此首先将堆的长度增加一个耽误，然后新增最后一个元素。因为只有新添加的节点可能不满足位置要求，因此对该节点执行上浮操作。具体做法是如果他的值小于其父母节点的值，那么交换两者的值，直到不满足条件为止，即可调整好最小堆。代码如下：

     function min_heap_insert(heap,name,data)
          %新增的节点添加的尾部
          heap.size=heap.size +1;
          heap.name(heap.size)=name;
          heap.data(heap.size)=data;
          %新增的节点做上浮的动作，达到排序的效果 
          heap_up_float(heap,heap.size);
      end
     function  heap_up_float(heap,self)
         while(self >=2)
             parent=floor(self/2);
             if(heap.data(self) < heap.data(parent))
                heap_swap_node(heap,parent,self); 
             end
             self =parent;
         end            
     end
            

执行my_heap.min_heap_insert(‘N’,3)后，运行结果如下：
node 1–>B–>1
node 2–>E–>1
node 3–>C–>1
node 4–>N–>3
node 5–>A–>10
node 6–>F–>1
node 7–>G–>8
node 8–>D–>11
node 9–>H–>5
图状表示如下：

从最小堆里面弹出最小的节点

取出最小节点仍然不能破坏最小堆的结构，方法是将根节点和最后一个节点交换，那么最后一个节点就最小的节点。然后将堆的长度减小1个单位，此时只有根节点可能不满足最小堆的特性，执行节点下沉算法，就可以满足要求。代码如下：

  function min_heap_popup(heap)
       heap_swap_node(heap,1,heap.size);%交换根节点和尾结点
        heap.size =heap.size -1;
        heap_down_sink(heap,1);%根节点下沉                
    end

执行my_heap.min_heap_popup()后运算结果如下：
node 1–>E–>1
node 2–>N–>3
node 3–>C–>1
node 4–>H–>5
node 5–>A–>10
node 6–>F–>1
node 7–>G–>8
node 8–>D–>11
图状表示如下

总结：以上就是最小堆的基本操作，欢迎探讨交流。

堆树的定义：

（1）堆树是一颗完全二叉树；

（2）堆树中某个节点的值总是不大于或不小于其孩子节点的值；

（3）堆树中每个节点的子树都是堆树。

当父节点的键值总是大于或等于任何一个子节点的键值时为最大堆。 当父节点的键值总是小于或等于任何一个子节点的键值时为最小堆。如下图所示，左边为最小堆，右边为最大堆。

数组与堆

无序数组转化成原始的二叉堆：

构建最小堆：

元素下沉思想：从无序数组的最后往前遍历，堆树从下层到上层依次搭建完成

1 从叶子节点（无序数组的最后一个元素）出发，把当前的parent设置为无序数组中的最后一个数（也就是叶子节点），依次往前遍历，当parent是叶子节点，就不做操作

2 当parent遍历到非叶子节点，此时，它就有左子节点和右子节点或者只有左子节点。需要做的操作：先在左右子节点中找到最小元素所在的索引，然后将左右子节点中的最小元素与parent的节点，进行比较，如果小于，则交换，同时更新parent和child的位置。否则不交换，退出当前循环。

3 “元素下沉”的终止条件就是父节点的元素值不大于其任意左右子节点的元素值，或者当前父节点无子节点（即当前节点为叶子节点）。

def heap_min(heap):
    for parent in range(len(heap)-1,-1,-1):
        child = 2*parent+1
        while child <len(heap):
            if child+1<len(heap) and heap[child+1]<heap[child]:
                child += 1
            if heap[parent]<= heap[child]:
                break
            heap[parent],heap[child] = heap[child],heap[parent]
            parent,child = child,2*child+1
    return heap
    
    
print(heap_min([4,5,3,2,6,1]))

输出结果是：构建了最小堆

堆排序：

是指利用堆（最大堆、最小堆）这种数据结构所设计的一种排序算法。堆是一个完全二叉树的结构，并同时满足如下性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

def sift_down(arr, start, end):
    root = start
    while True:
        # 从root开始对最大堆调整
        child = 2 * root + 1
        if child > end:
            break
        # 找出两个child中交大的一个
        if child + 1 <= end and arr[child] < arr[child + 1]:
            child += 1
        if arr[root] < arr[child]:
            # 最大堆小于较大的child, 交换顺序
            arr[root], arr[child] = arr[child], arr[root]
            # 正在调整的节点设置为root
            root = child
        else:
            # 无需调整的时候, 退出
            break


def heap_sort(arr):
    # 从最后一个有子节点的孩子还是调整最大堆
    first = len(arr) // 2 - 1
    for start in range(first, -1, -1):
        sift_down(arr, start, len(arr) - 1)
    # 将最大的放到堆的最后一个, 堆-1, 继续调整排序
    for end in range(len(arr) -1, 0, -1):
        arr[0], arr[end] = arr[end], arr[0]
        sift_down(arr, 0, end - 1)

def main():
    # [7, 95, 73, 65, 60, 77, 28, 62, 43]
    # [3, 1, 4, 9, 6, 7, 5, 8, 2, 10]
    l = [3, 1, 4, 9, 6, 7, 5, 8, 2, 10]
    print (l)
    heap_sort(l)
    print (l)


if __name__ == "__main__":
    main()