斜堆的C语言实现
斜堆(skew heap)是左倾堆的一个变种，与左倾堆一样，合并的时间复杂度也是O(lgn)。相对于左倾堆来说，斜堆没有零距离这个概念，而是在合并操作的时候，每次交换左右子树。
斜堆的定义
typedef struct skew_heap_s *skew_heap_pt;
typedef struct skew_heap_s {
skew_heap_pt left;
skew_heap_pt right;
Item data;
} skew_heap_t;
合并操作图解
与左倾堆相同，合并操作也是斜堆的重点。合并两个斜堆的过程如下：
- 如果一个空斜堆与非空斜堆合并，返回非空斜堆
- 如果两个斜都非空，比较两个根节点，取优先级高的根节点为新的根节点。将“优先级较高堆的根节点的右孩子”和“优先级底的堆”进行合并
- 合并后，交换新堆根节点的左孩子和右孩子
代码实现如下
skew_heap_pt
skew_heap_merge(skew_heap_pt h1, skew_heap_pt h2)
{
skew_heap_pt tmp;
if (h1 == NULL) {
return h2;
}
if (h2 == NULL) {
return h1;
}
/* 保证h1的优先级大于h2 */
if (item_cmp(h1->data, h2->data)) {
swap(h1, h2);
}
h1->right = skew_heap_merge(h1->right, h2);
tmp = h1->left;
h1->left = h1->right;
h1->right = tmp;
return h1;
}
流程如下图所示
完整源码
/* skew_heap.h */
#ifndef SKEW_HEAP_H
#define SKEW_HEAP_H
typedef int Item;
typedef struct skew_heap_s *skew_heap_pt;
typedef struct skew_heap_s {
skew_heap_pt left;
skew_heap_pt right;
Item data;
} skew_heap_t;
skew_heap_pt skew_heap_merge(skew_heap_pt h1, skew_heap_pt h2);
skew_heap_pt skew_heap_push(skew_heap_pt heap, Item element);
skew_heap_pt skew_heap_pop(skew_heap_pt heap);
Item skew_heap_top(skew_heap_pt heap);
void skew_heap_destroy(skew_heap_pt heap);
void skew_heap_print(skew_heap_pt heap);
void skew_heap_export_dot(skew_heap_pt heap, char *filename, char *label);
#endif
skew_heap.h
/* skew_heap.c */
/*
* =====================================================================================
*
* Filename: skew_heap.c
*
* Description: 斜堆实现
*
* Version: 1.0
* Created: 2016-09-25 12:09
* Revision: none
* Compiler: gcc
*
* Author: simon
*
* =====================================================================================
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "skew_heap.h"
static void
swap(skew_heap_pt p1, skew_heap_pt p2)
{
skew_heap_t temp;
temp = *p1;
*p1 = *p2;
*p2 = temp;
}
/*
* 最小堆 ((a) > (b))
* 最大堆 ({a} < (b))
*
*/
#define item_cmp(a, b) ((a) > (b)) /* 最小堆 */
skew_heap_pt
skew_heap_merge(skew_heap_pt h1, skew_heap_pt h2)
{
skew_heap_pt tmp;
if (h1 == NULL) {
return h2;
}
if (h2 == NULL) {
return h1;
}
/* 保证h1的优先级大于h2 */
if (item_cmp(h1->data, h2->data)) {
swap(h1, h2);
}
h1->right = skew_heap_merge(h1->right, h2);
tmp = h1->left;
h1->left = h1->right;
h1->right = tmp;
return h1;
}
skew_heap_pt
skew_heap_push(skew_heap_pt heap, Item element)
{
skew_heap_pt node_pt;
node_pt = (skew_heap_pt)malloc(sizeof(skew_heap_t));
if (node_pt == NULL) {
return heap;
}
node_pt->left = NULL;
node_pt->right = NULL;
node_pt->data = element;
return skew_heap_merge(heap, node_pt);
}
skew_heap_pt
skew_heap_pop(skew_heap_pt heap)
{
if (heap == NULL) {
return heap;
}
skew_heap_pt node_left_pt = heap->left;
skew_heap_pt node_right_pt = heap->right;
free(heap);
return skew_heap_merge(node_left_pt, node_right_pt);
}
Item
skew_heap_top(skew_heap_pt heap)
{
return heap->data;
}
void
skew_heap_destroy(skew_heap_pt heap)
{
if (heap == NULL) {
return;
}
skew_heap_destroy(heap->left);
skew_heap_destroy(heap->right);
free(heap);
}
static void
skew_heap_printnode(skew_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
skew_heap_show(skew_heap_pt heap, int h)
{
if (heap == NULL) {
skew_heap_printnode(heap, h);
return;
}
skew_heap_show(heap->left, h+1);
skew_heap_printnode(heap, h);
skew_heap_show(heap->right, h+1);
}
void
skew_heap_print(skew_heap_pt heap)
{
skew_heap_show(heap, 0);
}
/* 打印节点计数变量 */
static int node_num = 0;
static void
export_dot(FILE *fp, skew_heap_pt heap, char *last_label)
{
/* 打印节点 */
char node_name[10] = {0};
sprintf(node_name, "n%d", node_num);
if (heap == NULL) {
fprintf(fp, "%s[style=invis];\n", node_name);
}
else {
fprintf(fp, "%s[label=%d];\n", node_name, heap->data);
}
node_num++;
/* 打印边 */
if (last_label != NULL) {
if (heap == NULL) {
fprintf(fp, "%s->%s[style=invis];\n", last_label, node_name);
}
else {
fprintf(fp, "%s->%s;\n", last_label, node_name);
}
}
if (heap == NULL) {
return;
}
/* 打印子节点 */
if (heap->left == NULL && heap->right == NULL) {
return;
}
export_dot(fp, heap->left, node_name);
export_dot(fp, NULL, node_name);
export_dot(fp, heap->right, node_name);
}
void
skew_heap_export_dot(skew_heap_pt heap, char *filename, char *label)
{
FILE *fp;
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);
}
skew_heap.c
/* skew_heap_test.c */
#include <stdlib.h>
#include <stdio.h>
#include "skew_heap.h"
#define LENGTH(a) ( (sizeof(a)) / (sizeof(a[0])) )
int
main(int argc, char *argv[])
{
int a[]= {10,40,24,30,36,20,12,16};
int b[]= {17,13,11,15,19,21,23};
int i;
int alen=LENGTH(a);
int blen=LENGTH(b);
skew_heap_pt ha = NULL, hb = NULL, hc = NULL;
printf("== 斜堆(ha)中依次添加: ");
for(i=0; i<alen; i++)
{
printf("%d ", a[i]);
ha = skew_heap_push(ha, a[i]);
}
printf("\n== 斜堆(ha)的详细信息: \n");
skew_heap_print(ha);
printf("\n== 斜堆(hb)中依次添加: ");
for(i=0; i<blen; i++)
{
printf("%d ", b[i]);
hb = skew_heap_push(hb, b[i]);
}
printf("\n== 斜堆(hb)的详细信息: \n");
skew_heap_print(hb);
hc = skew_heap_merge(ha, hb);
printf("\n== 合并ha和hb后的详细信息: \n");
skew_heap_print(hc);
skew_heap_export_dot(hc, "skew1.dot", "合并结果图");
skew_heap_destroy(hc);
return 0;
}
skew_heap_test.c
测试程序的运行结果
== 斜堆(ha)中依次添加: 10 40 24 30 36 20 12 16
== 斜堆(ha)的详细信息:
*
40
*
30
*
20
*
16
*
10
*
36
*
24
*
12
*
== 斜堆(hb)中依次添加: 17 13 11 15 19 21 23
== 斜堆(hb)的详细信息:
*
23
*
17
*
13
*
19
*
11
*
21
*
15
*
== 合并ha和hb后的详细信息:
*
21
*
15
*
12
*
36
*
24
*
11
*
23
*
17
*
13
*
19
*
10
*
40
*
30
*
20
*
16
*
最后生成dot标记文件，然后使用工具可以生成下图
转载文章请注明出处： http://mingnote.com