左倾堆的C语言实现
左倾堆(leftist tree 或 leftist heap)又称为左式堆，左偏树，左偏堆，最左堆等。左倾堆是优先队列的一种实现方式，当优先队列需要解决“两个优先队列合并”的问题时，二叉堆的效率就比较差了，这时左倾堆等方式可以很好的解决这类问题。左倾堆合并时间复杂度为O(lgn)。左倾堆在统计问题，最值问题，模拟问题和贪心问题等问题中有广泛的应用。 左倾堆是二叉树，另外还有两个属性，键值和零距离。
键值用来比较节点的大小
零距离(NPL)是 null path length 的缩写，指的是从该结点到达一个没有两个孩子的结点（一个或无孩子）的最短距离，叶节点的NPL为0, NULL的NPL为-1。
左倾堆的性质
- 节点的优先级大于或等于它子节点的优先级
- 任意节点左孩子的NPL >= 右孩子的NPL
- 节点的NPL = 它的右孩子的NPL + 1
左倾堆的定义
typedef struct leftist_heap_s *leftist_heap_pt;
typedef struct leftist_heap_s {
leftist_heap_pt left;
leftist_heap_pt right;
Item data;
int npl;
} leftist_heap_t;
合并操作图解
合并操作是左倾堆的重点。合并两个左倾堆的过程如下：
- 如果一个空左倾堆与非空左倾堆合并，返回非空左倾堆
- 如果两个左倾堆都非空，比较两个根节点，取优先级高的根节点为新的根节点。将“优先级较高堆的根节点的右孩子”和“优先级底的堆”进行合并
- 如果新堆的右孩子的NPL > 左孩子的NPL，则交换左右孩子
- 设置新堆的根节点的NPL = 右子堆NPL + 1
代码实现如下
leftist_heap_pt
leftist_heap_merge(leftist_heap_pt h1, leftist_heap_pt h2)
{
leftist_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 = leftist_heap_merge(h1->right, h2);
if (h1->left == NULL || h1->right->npl > h1->left->npl) {
tmp = h1->left;
h1->left = h1->right;
h1->right = tmp;
}
if (h1->right == NULL || h1->left == NULL) {
h1->npl = 0;
}
else {
h1->npl = h1->right->npl + 1;
}
return h1;
}
流程如下图所示
完整源码
/* leftist_heap.h */
#ifndef LEFTIST_HEAP_H
#define LEFTIST_HEAP_H
typedef int Item;
typedef struct leftist_heap_s *leftist_heap_pt;
typedef struct leftist_heap_s {
leftist_heap_pt left;
leftist_heap_pt right;
Item data;
int npl;
} leftist_heap_t;
leftist_heap_pt leftist_heap_merge(leftist_heap_pt h1, leftist_heap_pt h2);
leftist_heap_pt leftist_heap_push(leftist_heap_pt heap, Item element);
leftist_heap_pt leftist_heap_pop(leftist_heap_pt heap);
Item leftist_heap_top(leftist_heap_pt heap);
void leftist_heap_destroy(leftist_heap_pt heap);
void leftist_heap_print(leftist_heap_pt heap);
void leftist_heap_export_dot(leftist_heap_pt heap, char *filename, char *label);
#endif
leftist_heap.h
/* leftist_heap.c */
/*
* =====================================================================================
*
* Filename: leftist_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 "leftist_heap.h"
static void
swap(leftist_heap_pt p1, leftist_heap_pt p2)
{
leftist_heap_t temp;
temp = *p1;
*p1 = *p2;
*p2 = temp;
}
/*
* 最小堆 ((a) > (b))
* 最大堆 ({a} < (b))
*
*/
#define item_cmp(a, b) ((a) > (b)) /* 最小堆 */
leftist_heap_pt
leftist_heap_merge(leftist_heap_pt h1, leftist_heap_pt h2)
{
leftist_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 = leftist_heap_merge(h1->right, h2);
if (h1->left == NULL || h1->right->npl > h1->left->npl) {
tmp = h1->left;
h1->left = h1->right;
h1->right = tmp;
}
if (h1->right == NULL || h1->left == NULL) {
h1->npl = 0;
}
else {
h1->npl = h1->right->npl + 1;
}
return h1;
}
leftist_heap_pt
leftist_heap_push(leftist_heap_pt heap, Item element)
{
leftist_heap_pt node_pt;
node_pt = (leftist_heap_pt)malloc(sizeof(leftist_heap_t));
if (node_pt == NULL) {
return heap;
}
node_pt->left = NULL;
node_pt->right = NULL;
node_pt->npl = 0;
node_pt->data = element;
return leftist_heap_merge(heap, node_pt);
}
leftist_heap_pt
leftist_heap_pop(leftist_heap_pt heap)
{
if (heap == NULL) {
return heap;
}
leftist_heap_pt node_left_pt = heap->left;
leftist_heap_pt node_right_pt = heap->right;
free(heap);
return leftist_heap_merge(node_left_pt, node_right_pt);
}
Item
leftist_heap_top(leftist_heap_pt heap)
{
return heap->data;
}
void
leftist_heap_destroy(leftist_heap_pt heap)
{
if (heap == NULL) {
return;
}
leftist_heap_destroy(heap->left);
leftist_heap_destroy(heap->right);
free(heap);
}
static void
leftist_heap_printnode(leftist_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
leftist_heap_show(leftist_heap_pt heap, int h)
{
if (heap == NULL) {
leftist_heap_printnode(heap, h);
return;
}
leftist_heap_show(heap->left, h+1);
leftist_heap_printnode(heap, h);
leftist_heap_show(heap->right, h+1);
}
void
leftist_heap_print(leftist_heap_pt heap)
{
leftist_heap_show(heap, 0);
}
/* 打印节点计数变量 */
static int node_num = 0;
static void
export_dot(FILE *fp, leftist_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, xlabel=%d];\n", node_name, heap->data, heap->npl);
}
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
leftist_heap_export_dot(leftist_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);
}
leftist_heap.c
/* leftist_heap_test.c */
#include <stdlib.h>
#include <stdio.h>
#include "leftist_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);
leftist_heap_pt ha = NULL, hb = NULL, hc = NULL;
printf("== 左倾堆(ha)中依次添加: ");
for(i=0; i<alen; i++)
{
printf("%d ", a[i]);
ha = leftist_heap_push(ha, a[i]);
}
printf("\n== 左倾堆(ha)的详细信息: \n");
leftist_heap_print(ha);
printf("\n== 左倾堆(hb)中依次添加: ");
for(i=0; i<blen; i++)
{
printf("%d ", b[i]);
hb = leftist_heap_push(hb, b[i]);
}
printf("\n== 左倾堆(hb)的详细信息: \n");
leftist_heap_print(hb);
hc = leftist_heap_merge(ha, hb);
printf("\n== 合并ha和hb后的详细信息: \n");
leftist_heap_print(hc);
leftist_heap_export_dot(hc, "leftist1.dot", "合并结果图");
leftist_heap_destroy(hc);
return 0;
}
leftist_heap_test.c
测试程序的运行结果
== 左倾堆(ha)中依次添加: 10 40 24 30 36 20 12 16
== 左倾堆(ha)的详细信息:
*
30
*
24
*
36
*
10
*
40
*
20
*
12
*
16
*
== 左倾堆(hb)中依次添加: 17 13 11 15 19 21 23
== 左倾堆(hb)的详细信息:
*
19
*
15
*
21
*
11
*
17
*
13
*
23
*
== 合并ha和hb后的详细信息:
*
19
*
15
*
21
*
11
*
17
*
13
*
23
*
16
*
12
*
40
*
20
*
10
*
30
*
24
*
36
*
最后生成dot标记文件，然后使用工具可以生成下图
转载文章请注明出处： http://mingnote.com