pairing堆的C语言实现
斐波那契堆编程实现难度较大并且效率没有理论的快(由于它的存储结构和四个指针)。pairing堆可以弥补斐波那契堆的缺点，编程比较简单且时间复杂度跟斐波那契堆相同。
pairing堆是一棵多路树，类似于左倾堆和斜堆，与二项堆和斐波那契堆不同。它的基本操作是两个多路树的连接，所以取名叫pairing堆。
关于pairing堆的完整中文资料比较少，但国外还是挺容易找到的。以下的实现参考cise.ufl.edu一些公开课资料的讲解。
pairing堆的数据结构定义
pairing堆的数据结构一般如下：
typedef struct pairing_heap_s *pairing_heap_pt;
typedef struct pairing_heap_s {
Item data;
pairing_heap_pt child;
pairing_heap_pt sibling;
pairing_heap_pt previous;
} pairing_heap_t;
child指向最左边的孩子;
sibling指向该节点右边的兄弟节点;
previous指向该节点的左边兄弟节点,当节点在最左边时，previous指向父节点。
斐波那契堆和pairing堆复杂度比较
斐波那契堆的复杂度如下：
pairing堆的复杂度如下：
但是许多研究都表明pairing堆的实际性能要好于斐波那契堆。
合并操作
合并操作比较简单，比较两个堆中根的值，把优先级较低的插入到优先级较高的子节点链表中的最左端。具体流程如下图所示。
以下为实现代码
pairing_heap_pt
pairing_heap_union(pairing_heap_pt h1, pairing_heap_pt h2)
{
pairing_heap_pt root, child;
if (h1 == NULL) {
return h2;
}
if (h2 == NULL) {
return h1;
}
if (item_cmp(h1->data, h2->data)) {
root = h2;
child = h1;
}
else {
root = h1;
child = h2;
}
child->sibling = root->child;
child->previous = root;
if (root->child != NULL) {
root->child->previous = child;
}
root->child = child;
return root;
}
插入操作
插入操作和合并是相同，使用新插入的元素建立一个新堆，然后再与原来的堆合并即可。
以下为实现代码
pairing_heap_pt
pairing_heap_push(pairing_heap_pt heap, Item element)
{
pairing_heap_pt node;
node = pairing_heap_new(element);
return pairing_heap_union(heap, node);
}
删除最小元素操作
这是pairing堆中最复杂的操作。其实就是把堆的根删掉，然后合并它的儿子节点。步骤如下
- 删除根节点，把根节点的所有子节点当成一个链表。
- 从左到右两两合并链表中的树。
- 再从右到左合并链表中的树。
- 直到链表中只剩下唯一的树，即是最后堆的根。
过程如下图所示：
以下为实现代码
/*
* Name: pairing_heap_subtree_pairing
* Description: 把树的子树两两合并直到变成一棵树
*
*/
static pairing_heap_pt
pairing_heap_subtree_pairing(pairing_heap_pt node)
{
pairing_heap_pt temp, pos, next;
node->previous = NULL;
pos = node;
temp = NULL;
/* left to right */
while (pos != NULL && pos->sibling != NULL) {
next = pos->sibling->sibling;
pos = pairing_heap_union(pos, pos->sibling);
/* 存入temp链表的右边 */
if (temp == NULL) {
pos->sibling = NULL;
pos->previous = NULL;
}
else {
pos->sibling = NULL;
pos->previous = temp;
temp->sibling = pos;
}
temp = pos;
if (next != NULL && next->sibling !=NULL) {
pos = next;
}
else {
/* 处理原链表尾部还有一个节点 */
if (next != NULL) {
temp->sibling = next;
next->previous = temp;
temp = next;
}
next = NULL;
/* right to left */
pos = temp;
temp = NULL;
while (pos != NULL && pos->previous != NULL) {
next = pos->previous->previous;
pos = pairing_heap_union(pos, pos->previous);
/* 存入temp链表的左边 */
if (temp == NULL) {
pos->sibling = NULL;
pos->previous = NULL;
}
else {
pos->sibling = temp;
pos->previous = NULL;
temp->previous = pos;
}
temp = pos;
pos = next;
}
if (temp != NULL) {
pos = temp;
/* 处理原链表尾部还有一个节点 */
if (next != NULL) {
temp->previous = next;
next->sibling = temp;
temp = next;
}
temp = NULL;
}
}
}
return pos;
}
pairing_heap_pt
pairing_heap_pop(pairing_heap_pt heap)
{
pairing_heap_pt node, temp, pos, next;
if (heap == NULL) {
return NULL;
}
node = heap->child;
free(heap);
if (node == NULL) {
return NULL;
}
return pairing_heap_subtree_pairing(node);
}
优先级增加
由于是最小堆，优先级增加表现为数据减小。步骤如下：
- 如果增加的值大于等于其父节点，则只修改值，树不变。
- 否则。把以该节点为根的树截取下来成为新的堆。
- 把截取的新堆与根合并。
具体操作如下图：
以下为实现代码
/*
* Name: pairing_heap_increase
* Description: 值变化使节点优先级更高时对树进行调整
*
*/
static pairing_heap_pt
pairing_heap_increase(pairing_heap_pt heap, pairing_heap_pt node)
{
pairing_heap_pt parent, pos;
if (heap == node) {
return heap;
}
/* 取得父节点 */
pos = node;
parent = pos->previous;
while (parent->child != pos) {
pos = parent;
parent = pos->previous;
}
if (!item_cmp(parent->data, node->data)) {
return heap;
}
/* 从堆中移除节点 */
pairing_node_remove(node, parent);
return pairing_heap_union(heap, node);
}
优先级减少
由于是最小堆，优先级增加表现为数据增大。操作与二 叉树的向下堆化相同。递归地交换当前节点与子节点中的最小值， 直到满足堆的特性(所有子树都比父大)。
如下图所示:
以下为实现代码
/*
* Name: pairing_heap_fixdown
* Description: 值变化优先级更低时，向下调整树
*
*/
static void
pairing_heap_fixdown(pairing_heap_pt node)
{
pairing_heap_pt best, pos;
if (node == NULL || node->child == NULL) {
return;
}
pos = node->child;
for (best = pos; pos != NULL; pos = pos->sibling) {
if (item_cmp(best->data, pos->data)) {
best = pos;
}
}
if (item_cmp(node->data, best->data)) {
swap(&node->data, &best->data);
pairing_heap_fixdown(best);
}
}
删除操作
- 寻找到所要删除的节点，如果是根节点，则与pop操作相同。
- 把找到的节点从树中移除，通过两两合并的方法把该节点的所有子树变成一个新的堆。
- 合并新堆与原来的堆，即完成删除操作。
如下图所示：
以下为实现代码
pairing_heap_pt
pairing_heap_delete(pairing_heap_pt heap, Item element)
{
pairing_heap_pt node, parent, pos, newheap;
if (heap == NULL) {
return NULL;
}
node = pairing_heap_find(heap, element);
if (node == NULL) {
return heap;
}
if (heap == node) {
return pairing_heap_pop(heap);
}
/* 取得父节点 */
pos = node;
parent = pos->previous;
while (parent->child != pos) {
pos = parent;
parent = pos->previous;
}
pairing_node_remove(node, parent);
newheap = pairing_heap_subtree_pairing(node->child);
free(node);
return pairing_heap_union(heap, newheap);
}
完整源码
/* pairing_heap.h */
#ifndef PAIRING_HEAP_H
#define PAIRING_HEAP_H
typedef int Item;
typedef struct pairing_heap_s *pairing_heap_pt;
typedef struct pairing_heap_s {
Item data;
pairing_heap_pt child;
pairing_heap_pt sibling;
pairing_heap_pt previous;
} pairing_heap_t;
pairing_heap_pt pairing_heap_new(Item element);
int pairing_heap_top(pairing_heap_pt heap, Item *value);
pairing_heap_pt pairing_heap_union(pairing_heap_pt h1, pairing_heap_pt h2);
pairing_heap_pt pairing_heap_push(pairing_heap_pt heap, Item element);
pairing_heap_pt pairing_heap_pop(pairing_heap_pt heap);
pairing_heap_pt pairing_heap_update(pairing_heap_pt heap, Item oldelement, Item newelement);
pairing_heap_pt pairing_heap_delete(pairing_heap_pt heap, Item element);
void pairing_heap_destroy(pairing_heap_pt heap);
void pairing_heap_print(pairing_heap_pt heap);
void pairing_heap_export_dot(pairing_heap_pt heap, char *filename, char *label);
#endif
pairing_heap.h
/* pairing_heap.c */
/*
* =====================================================================================
*
* Filename: pairing_heap.c
*
* Description: pairing堆实现
*
* Version: 1.0
* Created: 2016-10-06 18:29
* Revision: none
* Compiler: gcc
*
* Author: simon
*
* =====================================================================================
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "pairing_heap.h"
/*
* 最小堆 ((a) > (b))
* 最大堆 ({a} < (b))
*
*/
#define item_cmp(a, b) ((a) > (b)) /* 最小堆 */
#define item_equal(a, b) ((a) == (b)) /* 相等比较 */
static void swap(Item *a, Item *b);
static pairing_heap_pt pairing_heap_subtree_pairing(pairing_heap_pt node);
static pairing_heap_pt pairing_heap_find(pairing_heap_pt heap, Item element);
static void pairing_node_remove(pairing_heap_pt node, pairing_heap_pt parent);
static pairing_heap_pt pairing_heap_increase(pairing_heap_pt heap, pairing_heap_pt node);
static void pairing_heap_fixdown(pairing_heap_pt node);
static void pairing_heap_printnode(pairing_heap_pt node, int h);
static void pairing_heap_show(pairing_heap_pt heap, int h);
static void export_dot(FILE *fp, pairing_heap_pt heap, char *last_label);
static void
swap(Item *a, Item *b)
{
Item c;
c = *a;
*a = *b;
*b = c;
}
pairing_heap_pt
pairing_heap_new(Item element)
{
pairing_heap_pt heap;
heap = (pairing_heap_pt)malloc(sizeof(pairing_heap_t));
heap->data = element;
heap->child = NULL;
heap->sibling = NULL;
heap->previous = NULL;
return heap;
}
int
pairing_heap_top(pairing_heap_pt heap, Item *value)
{
if (heap == NULL) {
return 0;
}
else {
*value = heap->data;
return 1;
}
}
pairing_heap_pt
pairing_heap_union(pairing_heap_pt h1, pairing_heap_pt h2)
{
pairing_heap_pt root, child;
if (h1 == NULL) {
return h2;
}
if (h2 == NULL) {
return h1;
}
if (item_cmp(h1->data, h2->data)) {
root = h2;
child = h1;
}
else {
root = h1;
child = h2;
}
child->sibling = root->child;
child->previous = root;
if (root->child != NULL) {
root->child->previous = child;
}
root->child = child;
return root;
}
pairing_heap_pt
pairing_heap_push(pairing_heap_pt heap, Item element)
{
pairing_heap_pt node;
node = pairing_heap_new(element);
return pairing_heap_union(heap, node);
}
/*
* Name: pairing_heap_subtree_pairing
* Description: 把树的子树两两合并直到变成一棵树
*
*/
static pairing_heap_pt
pairing_heap_subtree_pairing(pairing_heap_pt node)
{
pairing_heap_pt temp, pos, next;
node->previous = NULL;
pos = node;
temp = NULL;
/* left to right */
while (pos != NULL && pos->sibling != NULL) {
next = pos->sibling->sibling;
pos = pairing_heap_union(pos, pos->sibling);
/* 存入temp链表的右边 */
if (temp == NULL) {
pos->sibling = NULL;
pos->previous = NULL;
}
else {
pos->sibling = NULL;
pos->previous = temp;
temp->sibling = pos;
}
temp = pos;
if (next != NULL && next->sibling !=NULL) {
pos = next;
}
else {
/* 处理原链表尾部还有一个节点 */
if (next != NULL) {
temp->sibling = next;
next->previous = temp;
temp = next;
}
next = NULL;
/* right to left */
pos = temp;
temp = NULL;
while (pos != NULL && pos->previous != NULL) {
next = pos->previous->previous;
pos = pairing_heap_union(pos, pos->previous);
/* 存入temp链表的左边 */
if (temp == NULL) {
pos->sibling = NULL;
pos->previous = NULL;
}
else {
pos->sibling = temp;
pos->previous = NULL;
temp->previous = pos;
}
temp = pos;
pos = next;
}
if (temp != NULL) {
pos = temp;
/* 处理原链表尾部还有一个节点 */
if (next != NULL) {
temp->previous = next;
next->sibling = temp;
temp = next;
}
temp = NULL;
}
}
}
return pos;
}
pairing_heap_pt
pairing_heap_pop(pairing_heap_pt heap)
{
pairing_heap_pt node, temp, pos, next;
if (heap == NULL) {
return NULL;
}
node = heap->child;
free(heap);
if (node == NULL) {
return NULL;
}
return pairing_heap_subtree_pairing(node);
}
/*
* Name: pairing_heap_find
* Description: 查找指定元素的节点
*
*/
static pairing_heap_pt
pairing_heap_find(pairing_heap_pt heap, Item element)
{
pairing_heap_pt node;
if (heap == NULL) {
return NULL;
}
if (item_equal(heap->data, element)) {
return heap;
}
if ((node = pairing_heap_find(heap->child, element)) != NULL) {
return node;
}
if ((node = pairing_heap_find(heap->sibling, element)) != NULL) {
return node;
}
return NULL;
}
/*
* Name: pairing_node_remove
* Description: 从树的儿子链表中删除节点
*
*/
static void
pairing_node_remove(pairing_heap_pt node, pairing_heap_pt parent)
{
if (parent->child == node) {
parent->child = node->sibling;
}
else {
node->previous->sibling = node->sibling;
}
if (node->sibling != NULL) {
node->sibling->previous = node->previous;
}
node->sibling = NULL;
node->previous = NULL;
}
/*
* Name: pairing_heap_increase
* Description: 值变化使节点优先级更高时对树进行调整
*
*/
static pairing_heap_pt
pairing_heap_increase(pairing_heap_pt heap, pairing_heap_pt node)
{
pairing_heap_pt parent, pos;
if (heap == node) {
return heap;
}
/* 取得父节点 */
pos = node;
parent = pos->previous;
while (parent->child != pos) {
pos = parent;
parent = pos->previous;
}
if (!item_cmp(parent->data, node->data)) {
return heap;
}
/* 从堆中移除节点 */
pairing_node_remove(node, parent);
return pairing_heap_union(heap, node);
}
/*
* Name: pairing_heap_fixdown
* Description: 值变化优先级更低时，向下调整树
*
*/
static void
pairing_heap_fixdown(pairing_heap_pt node)
{
pairing_heap_pt best, pos;
if (node == NULL || node->child == NULL) {
return;
}
pos = node->child;
for (best = pos; pos != NULL; pos = pos->sibling) {
if (item_cmp(best->data, pos->data)) {
best = pos;
}
}
if (item_cmp(node->data, best->data)) {
swap(&node->data, &best->data);
pairing_heap_fixdown(best);
}
}
pairing_heap_pt
pairing_heap_update(pairing_heap_pt heap, Item oldelement, Item newelement)
{
pairing_heap_pt node;
if (heap == NULL) {
return NULL;
}
node = pairing_heap_find(heap, oldelement);
if (node == NULL) {
return heap;
}
node->data = newelement;
if (item_cmp(oldelement, newelement)) {
return pairing_heap_increase(heap, node);
}
else {
pairing_heap_fixdown(node);
return heap;
}
}
pairing_heap_pt
pairing_heap_delete(pairing_heap_pt heap, Item element)
{
pairing_heap_pt node, parent, pos, newheap;
if (heap == NULL) {
return NULL;
}
node = pairing_heap_find(heap, element);
if (node == NULL) {
return heap;
}
if (heap == node) {
return pairing_heap_pop(heap);
}
/* 取得父节点 */
pos = node;
parent = pos->previous;
while (parent->child != pos) {
pos = parent;
parent = pos->previous;
}
pairing_node_remove(node, parent);
newheap = pairing_heap_subtree_pairing(node->child);
free(node);
return pairing_heap_union(heap, newheap);
}
void
pairing_heap_destroy(pairing_heap_pt heap)
{
if (heap == NULL) {
return;
}
pairing_heap_destroy(heap->child);
pairing_heap_destroy(heap->sibling);
free(heap);
}
static void
pairing_heap_printnode(pairing_heap_pt node, int h)
{
int i;
for (i=0; i < h; i++) {
printf(" ");
}
if (node == NULL) {
printf("*\n");
}
else {
printf("%d\n", node->data);
}
}
static void
pairing_heap_show(pairing_heap_pt heap, int h)
{
if (heap == NULL) {
pairing_heap_printnode(heap, h);
return;
}
pairing_heap_show(heap->child, h+1);
pairing_heap_printnode(heap, h);
pairing_heap_show(heap->sibling, h);
}
void
pairing_heap_print(pairing_heap_pt heap)
{
pairing_heap_show(heap, 0);
}
/* 打印节点计数变量 */
static int node_num = 0;
static void
export_dot(FILE *fp, pairing_heap_pt heap, char *last_label)
{
/* 打印节点 */
char node_name[10] = {0};
if (heap == NULL) {
return;
}
sprintf(node_name, "n%d", node_num);
fprintf(fp, "%s[label=%d];\n", node_name, heap->data);
node_num++;
/* 打印边 */
if (last_label != NULL) {
fprintf(fp, "%s->%s;\n", last_label, node_name);
}
/* 打印子节点 */
if (heap->child == NULL && heap->sibling == NULL) {
return;
}
/* 打印兄弟节点 */
export_dot(fp, heap->sibling, last_label);
/* 打印子节点 */
export_dot(fp, heap->child, node_name);
}
void
pairing_heap_export_dot(pairing_heap_pt heap, char *filename, char *label)
{
FILE *fp;
int cluster_num = 0;
char tree_name[10] = {0};
char last_tree_name[10] = {0};
fp = fopen(filename, "w");
fprintf(fp, "digraph g{\nnode[shape=circle];\nlabel=\"%s\";\nlabeljust=l;\nlabelloc=t;\n", label);
export_dot(fp, heap, NULL);
fprintf(fp, "}\n");
fclose(fp);
}
pairing_heap.c
/* pairing_heap_test.c */
#include <stdlib.h>
#include <stdio.h>
#include "pairing_heap.h"
#define LENGTH(a) ( (sizeof(a)) / (sizeof(a[0])) )
int
main(int argc, char *argv[])
{
int a[] = {3, 52, 38, 41, 19, 30, 39, 18};
int b[] = {26, 35, 24, 46, 4};
int i;
int alen;
int blen;
int value;
pairing_heap_pt ha = NULL, hb = NULL, hc = NULL;
alen=LENGTH(a);
printf("== pairing堆(ha)中依次添加: ");
for(i=0; i<alen; i++)
{
printf("%d ", a[i]);
ha = pairing_heap_push(ha, a[i]);
}
printf("\n== pairing堆(ha)的详细信息: \n");
pairing_heap_print(ha);
blen=LENGTH(b);
printf("== pairing堆(hb)中依次添加: ");
for(i=0; i<blen; i++)
{
printf("%d ", b[i]);
hb = pairing_heap_push(hb, b[i]);
}
printf("\n== pairing堆(hb)的详细信息: \n");
pairing_heap_print(hb);
hc = pairing_heap_union(ha, hb);
printf("\n== pairing堆(hc)的详细信息: \n");
pairing_heap_print(hc);
pairing_heap_export_dot(hc, "union.dot", "合并图");
printf("\n== pairing堆(hc)的移除顶部后详细信息: \n");
pairing_heap_print(hc);
pairing_heap_export_dot(hc, "pop.dot", "删除顶部值");
hc = pairing_heap_update(hc, 38, 12);
printf("\n== pairing堆(hc)的38变更为12详细信息: \n");
pairing_heap_print(hc);
pairing_heap_export_dot(hc, "increase.dot", "优先级增加");
hc = pairing_heap_update(hc, 24, 60);
printf("\n== pairing堆(hc)的24变更为60详细信息: \n");
pairing_heap_print(hc);
pairing_heap_export_dot(hc, "decrease.dot", "优先级减少");
hc = pairing_heap_delete(hc, 26);
printf("\n== pairing堆(hc)的删除26详细信息: \n");
pairing_heap_print(hc);
pairing_heap_export_dot(hc, "delete.dot", "删除节点");
pairing_heap_destroy(hc);
return 0;
}
pairing_heap_test.c
测试程序的运行结果
== pairing堆(ha)中依次添加: 3 52 38 41 19 30 39 18
== pairing堆(ha)的详细信息:
*
18
*
39
*
30
*
19
*
41
*
38
*
52
*
3
*
== pairing堆(hb)中依次添加: 26 35 24 46 4
== pairing堆(hb)的详细信息:
*
46
*
35
*
26
*
24
*
4
*
== pairing堆(hc)的详细信息:
*
46
*
35
*
26
*
24
*
4
*
18
*
39
*
30
*
19
*
41
*
38
*
52
*
3
*
== pairing堆(hc)的移除顶部后详细信息:
*
46
*
35
*
26
*
24
*
4
*
18
*
39
*
30
*
19
*
41
*
38
*
52
*
3
*
== pairing堆(hc)的38变更为12详细信息:
*
46
*
35
*
26
*
24
*
4
*
18
*
39
*
30
*
19
*
41
*
12
*
52
*
3
*
== pairing堆(hc)的24变更为60详细信息:
*
46
*
60
*
35
*
26
*
4
*
18
*
39
*
30
*
19
*
41
*
12
*
52
*
3
*
== pairing堆(hc)的删除26详细信息:
*
46
*
60
*
35
*
4
*
18
*
39
*
30
*
19
*
41
*
12
*
52
*
3
*
最后生成dot标记文件，然后使用工具可以生成下图
转载文章请注明出处： http://mingnote.com