浅析二叉堆(BinMaxHeap)

版权声明:本文为奥维原创文章,未经允许不得转载。

用markdown的时候标题符号后面记得加空格 ~fuck~

二叉堆简介

二叉堆是一种常见的数据结构,用这种数据结构去实现优先队列是一种很普遍的行为。而优先队列在我们的实际中有着各种各样的应用(如操作系统中的进程管理等等),今天就主要给大家浅析一下这种数据结构。

二叉堆是一种基于二叉树实现的堆类型数据结构。但是相比于普通的二叉树,二叉堆有两个限制,分别如下:

  • Shape property(结构性): 二叉堆首先是一个完全二叉树,完全二叉树(Complete Binary Tree)。

    完全二叉树:二叉树的深度为n,除第 n 层外,其它各层 (1~h-1) 的结点数都为2个,第 h 层所有的结点都连续集中在最左边

  • Heap property (堆序性): 所有的节点都大于等于或者小于等于它的子节点。根据堆序性,可以列出下面的常见的两种二叉堆图。

Binary Min Heap:

Binary Min Heap

Binary Max Heap:

Binary Max Heap

二叉堆的基本实现思路

二叉堆因为其利用了完全二叉树(二叉堆的结构特性)的原因,所以他的结构非常有特点,我们完全可以用一个数组存储其中的数据而不需要使用指针进行存储,因为我们可以很方便的索引到数组中元素的位置。如果我们自上而下,自左至右给一个二叉堆标序号,如图所示.

s

那么,我们可以很容易的发现,如果我们使用一个数组来存放这个二叉堆中的数据,那么对于这个数组中任意一个位置为i的元素,只要他有儿子,那么他的左二子就在下标为 2 i 的位置上,他的右儿子就在下标为 2 i + 1的位置上,这样,我们就可以很方便的去索引到我们需要访问的某一元素。
二叉堆与数组中的存储位置对应如下

img

img

二叉堆的基本操作说明

基本操作是两种,分别是插入和删除。由于二叉堆一般可以用于实现优先队列,所以删除实际上是删除最大(或最小值)。除了insert和deleteMax两种基本操作之外,还有buildHeap,decreaseKey,increaseKey等等一些常见操作

  • insert(插入操作):
    以这张图为例

    img

    假设我们要插入一个128的数,过程大约是这样的:
    首先我们将128插入到二叉堆的数组的末尾
    img

然后,我们需要让新插入的128和他的父亲(7)作比较,因为128比7大,为了维持二叉堆的堆序性,我们需要将7和128做一个交换,交换之后变成这样
img
接着我们需要继续用128和他的父亲(26)作比较,因为128比26大,为了维持二叉堆的堆序性,我们需要将26和128做一个交换,交换之后变成这样
img

  • 此时我们发现128终于被成功插入了,插入操作也就基本完成了

    在上述这种操作中,我们将我们需要插入的新元素128不断与从插入点开始到根(root)这条路径上的节点进行比较,如果发现128比他的父节点要大,那么我们就进行一次交换(swap),直到有一次,我们需要插入的节点(这里是128)并没有他的父节点大,那么我们就算插入成功,否则我们就一直比较到root节点为止

    注意:实际实现的时候由于交换效率比较低,所以我们会使用一个稍微巧妙一点的方法,避免这种交换,具体可以看下面的代码

  • deleteMax(删除操作):
    继续以刚才的图示为例讲解删除最大值(出队)操作
    img
    首先我们将最上面的128(最大值)删除
    img
    这个时候,二叉堆肯定是不满足上述的堆序性和结构性的,所以我们需要做调整。怎么调整呢?通过此时二叉堆的数组中的最后一个元素进行调整,我们需要将最后一个元素放在一个正确的位置。
    第一步,我们需要找出原来128的儿子节点中较大的一个(26),并且将他向上移动到128的一个位置。此时26的位置就空下来了,我们的7就可以放到原来26的位置上,这样,我们就算删除成功了。
    img

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
#include <stdio.h>
#include <stdlib.h>
struct HeapStruct;
typedef struct HeapStruct *PriorityQueue;
struct HeapStruct
{
int size;
int capacity;
int *elements;
};

PriorityQueue initialize(int maxSize);
PriorityQueue buildHeap(int *numbers, int size);
int deleteMax(PriorityQueue h);
void insert(int element, PriorityQueue h);
void decreaseKey(int pos, int delta, PriorityQueue h);
void increaseKey(int pos, int delta, PriorityQueue h);
void percolateUp(PriorityQueue h, int index);
void percolateDown(PriorityQueue h, int index);
void printBinHeap(PriorityQueue h);

void insert(int element, PriorityQueue h)
{

int index;
int parent;
for (index = ++h->size; index > 1; index = parent)
{
//相当于parent = index / 2
parent = index >> 1;
if (h->elements[parent] < element)
{
h->elements[index] = h->elements[parent];
} else
{
break;
}
}
h->elements[index] = element;
}
PriorityQueue initialize(int maxSize)
{
PriorityQueue priorityQueue = (PriorityQueue)malloc(sizeof(struct HeapStruct));
priorityQueue->capacity = maxSize;
priorityQueue->size = 0;
priorityQueue->elements = (int *)malloc(sizeof(int *) * maxSize);
return priorityQueue;
}
int deleteMax(PriorityQueue h)
{

int maxElement = h->elements[1];
int lastElement = h->elements[h->size--];
int index, child;
for (index = 1; index << 1 <= h->size; index = child)
{
//相当于child = index * 2
child = index << 1;
if (child != h->size && h->elements[child + 1] > h->elements[child])
{
child++;
}
if (h->elements[child] > lastElement)
{
h->elements[index] = h->elements[child];
} else
{
break;
}
}
h->elements[index] = lastElement;
return maxElement;
}

void decreaseKey(int pos, int delta, PriorityQueue h)
{
h->elements[pos] -= delta;
percolateDown(h, pos);
}
void increaseKey(int pos, int delta, PriorityQueue h)
{
h->elements[pos] += delta;
percolateUp(h, pos);
}
PriorityQueue buildHeap(int *numbers, int size)
{
PriorityQueue priorityQueue = initialize(size * 2);
for (int i = 0; i < size; i++)
{
priorityQueue->elements[i + 1] = numbers[i];
// printf("number[%d] %d\n",i + 1, priorityQueue->elements[i + 1]);
}
priorityQueue->size = size;
for (int i = size / 2; i >= 1; i--)
{
// printf("%d\n", priorityQueue->elements[i]);
percolateDown(priorityQueue, i);
}
return priorityQueue;
}
void percolateUp(PriorityQueue h, int index)
{
int tmp = h->elements[index];
int i = 0;
int parent = 0;
for (i = index; i > 1; i = parent)
{
//相当于parent = i / 2;
parent = i >> 1;
if (h->elements[parent] < tmp)
{
h->elements[i] = h->elements[parent];
} else
{
break;
}
}
h->elements[i] = tmp;
}
void percolateDown(PriorityQueue h, int index)
{
// printf("index = %d\n", index);
int tmp = h->elements[index];
// printf("tmp==%d\t", tmp);
int child = 0;
int i = 0;
for (i = index; i * 2 <= h->size; i = child)
{
//相当于 child = i * 2;
child = i * 2;
if (child != h->size && h->elements[child + 1] > h->elements[child])
{
child++;
}
if (tmp < h->elements[child])
{
h->elements[i] = h->elements[child];
} else
{
break;
}
}
// printf("tmp=%d\n", tmp);
h->elements[i] = tmp;
}
void printBinHeap(PriorityQueue h)
{
for (int i = 1; i <= h->size; i++)
{
printf("%d\n", h->elements[i]);
}
}

参考

  • Data Structure & Algorithm Analysis in C
  • wiki
啦啦啦啦啦啦