左高樹(leftist tree)將樹中的節點分為兩類：外部節點：用於代替樹中的空子樹；其餘節點均叫做內部節點．內部節點就是我們所能看到的樹中的每個真實節點，如果某個節點的左子樹為空，那它的這個左子樹就是外部節點．外部節點的引入，其實主要是為了下面s(x)這個概念的計算，並不具備其它實際意義．
基本介紹
- 中文名：高度優先左高樹
- 外文名：Height-Biased Leftist Tree
作用,代碼,
作用
為了更好的支持堆之間的合併。定義shortest(x)為從x到一個外部節點的最短路徑。
左高樹：是一顆二叉樹，如果該二叉樹不為空，則對於其中的每個節點x，都有shortest(left_child(x))>=shortest(right_child(x))。
代碼
以下實現的是最小左高樹的合併，插入，刪除最小值:插入可以看成一顆左高樹和一顆只有一個節點的左高樹的合併，刪除最小值可以看成該值所對應的左樹和右樹的合併。
#include <stdio.h>#include <stdlib.h>struct element { int key;};struct leftist { element data; leftist *left_child; leftist *right_child; int shortest;};void swap(leftist *&a, leftist *&b){ leftist *temp = a; a = b; b = temp;}void min_union(leftist *&a, leftist *&b){ if(a->data.key > b->data.key) { swap(a, b); } if(a->right_child == NULL) { a->right_child = b; } else { min_union(a->right_child, b); } if(a->left_child == NULL) { a->left_child = a->right_child; a->right_child = NULL; } else if(a->left_child->shortest < a->right_child->shortest) { swap(a->left_child, a->right_child); } a->shortest = (a->right_child == NULL) ? 1: a->right_child->shortest + 1;}void min_combine(leftist *&a, leftist *&b){ if(a == NULL) a = b; else if(b != NULL) { min_union(a, b); b = NULL; }}void insert(leftist *&a, leftist *&b){ min_combine(a, b);}element del_min(leftist *&a){ element temp = a->data; min_combine(a->left_child, a->right_child); a = a->left_child; return temp;}#define maxsize 100struct queue { leftist *queue[maxsize]; int front; int rear;};void initqueue(queue *q){ q->front = 0; q->rear = 0;}void addqueue(queue *q, leftist *root){ if((q->rear+1)%maxsize == q->front) { printf("queue full\n"); exit(1); } q->queue[q->rear] = root; q->rear = (q->rear+1)%maxsize;}void delqueue(queue *q, leftist *&root){ if(q->front == q->rear) { printf("queue empty\n"); exit(1); } root = q->queue[q->front]; q->front = (q->front+1)%maxsize;}void level(leftist *a){ queue q; initqueue(&q); addqueue(&q, a); while(q.front != q.rear) { delqueue(&q, a); printf("%d ", a->data.key); if(a->left_child != NULL) addqueue(&q, a->left_child); if(a->right_child != NULL) addqueue(&q, a->right_child); }}int main(){ leftist *a = NULL; for(int i=1; i<10; ++i) { leftist *p = new leftist; p->left_child = p->right_child = NULL; p->shortest = 1; p->data.key = i; insert(a, p); } del_min(a); level(a); printf("\n");}