图解堆排序算法

雨乐雨欣

原标题：图解堆排序算法

01

演进

结点和边，构成一个图。

不含环的连通图，便成了一棵树。每个结点拥有的子结点数称为结点的度。

多棵树便构成了一个丛林。

睁开全文

结点的度最大为2的树便是二叉树；最漂亮为N的是N叉树，或多叉树。

除叶子结点，每个结点的度都为2，称为满二叉树。

撤除末了一层之后的子树为满二叉树，且末了一层结点依次从左到右分布，则称为完全二叉树。

假如在完全二叉树上再加一个限定条件：如结点都大于即是其子结点，大概小于即是其子结点，则称为堆。

每个结点都大于即是其子结点，称为大根堆。

每个结点都小于即是其子结点，称为小根堆。

02

堆存储

2.1

次序存储：数组

用数组存储，将一个线性数组映射成一棵完全二叉树，父结点为i，则左儿子为2i+1，右儿子为2i+2。

代码如下

intheap[ 10];

2.2

链式存储：链表

界说一个结点的布局体，两个指针分别指向左儿子和右儿子。

代码如下

structNode{

intvalue;

Node *lson, *rson;

};

Node *heap;

以下头脑都以大根堆举例

03

堆调解

3.1

向上调解

子结点与父结点的下标关系如下：

用一个指针指向待调解的结点：

• 先比力是否大于父结点，假如大于就举行互换，并将指针上移到父结点

先比力是否大于父结点，假如大于就举行互换，并将指针上移到父结点

直到指向根结点大概当前结点小于即是父结点。

代码实现

//将heap[k]向上调解

intheapUp( int*heap, intk) {

intparent, son, x;

x = heap[k];

son = k;

parent = (son - 1) / 2;

while(son > 0) {

//假如父结点大于即是heap[k]则退出，否则将父结点下移

if(heap[parent] >= x)

break;

heap[son] = heap[parent];

son = parent;

parent = (son - 1) / 2;

}

heap[son] = x;

return0;

}

3.2

向下调解

父结点与子结点的下标关系如下：

用一个指针指向待调解的结点：

• 先比力两个子结点哪个更大，取出更大的子结点

先比力两个子结点哪个更大，取出更大的子结点

• 再比力更大的子结点是否大于父结点，假如大于就举行互换，并将指针下移

再比力更大的子结点是否大于父结点，假如大于就举行互换，并将指针下移

直到指向叶子结点大概当前结点大于两个子结点。

代码实现

//将heap[k]向下调解

intheapDown( int*heap, intk, intn) {

intparent, son, x;

x = heap[k];

parent = k;

son = 2* k + 1; //左孩子结点

while(son <= n) {

//比力左右儿子，选择较大的一个

if(son + 1<= n && heap[son + 1] > heap[son])

son++; //使son指向左右孩子中较大的结点。

//假如儿子结点中较大的都小于即是待调解结点则退出，否则将子结点上移

if(heap[son] <= x)

break;

heap[parent] = heap[son];

parent = son;

son = 2* parent + 1;

}

heap[parent] = x;

return0;

}

04

增减元素

4.1

PUSH

从堆尾插入元素，再对该元素举行向上调解直到满意堆性子。

4.2

POP

将堆顶弹出，用堆尾的元素置换，再对堆顶的元素举行向下调解。

05

构建堆

5.1

插入构建

依次向堆尾插入元素，并对该元素举行向上调解，直到满意堆性子。

时间复杂度：

插入一个元素要调解的高度为logi，以是插入n个元素的总次数为log1+log2+...+logn=log(n!)。

根据斯特林公式，有如下证实，以是复杂度O(nlogn)。

5.2

调解构建

待调解的数组，可以直接当作是一棵完全二叉树。

从(n-1)/2位置开始，将每个元素举行向下调解，直到根结点。对于每一个待调解的当前结点，下面的子树都已经满意堆性子，以是调解完全部结点便成了堆。

时间复杂度：

倒数第二层有2^(h-2)个结点，调解高度为1，依次类推，第一层有1个结点，调解高度为h-1，团体加起来的复杂度为O(n)。

代码实现

voidbuildHeap( int*heap, intn) {

for( inti = (n - 1) / 2; i >= 0; --i) {

heapDown(heap, i, n);

}

}

06

排序

一个已经调解完成的大根堆。

焦点头脑：

• 将堆顶与堆尾的元素置换

将堆顶与堆尾的元素置换

• 团体元素长度减1

• 对堆顶元素举行向下调解

团体元素长度减1

对堆顶元素举行向下调解

重复以上过程直到团体元素为1，这时就酿成了一个升序分列的数组。

模仿过程：

Step 1

Step 2

代码实现

voidswap( int*heap, inta, intb) {

inttemp;

temp = heap[a];

heap[a] = heap;

heap = temp;

}

voidheapsort( int*heap, intn) {

for( inti = n; i > 0; --i) {

swap(heap, 0, i);

heapDown(heap, 0, i - 1);

}

}

07

总结

堆排的复杂度为nlogn，应用场景很广泛，这篇文章重要讲清晰堆相干的操纵，详细的应用和建模以后会再专门写文章解说。返回搜狐，检察更多

责任编辑：