手撕⼆叉树——堆

1.2 树相关术语

1.3 树的表⽰

struct TreeNode
{struct Node* child; // 左边开始的第⼀个孩⼦结点struct Node* brother; // 指向其右边的下⼀个兄弟结点int data; // 结点中的数据域
};

1.4 树形结构实际运⽤场景

2. ⼆叉树

2.1 概念与结构

现实中的⼆叉树

2.2 特殊的⼆叉树

2.2.1 满⼆叉树

2.2.2 完全⼆叉树

💡 ⼆叉树性质

        根据满⼆叉树的特点可知：

        1）若规定根结点的层数为 1 ，则⼀棵⾮空⼆叉树的第i层上最多有 2 i −1 个结点

        2）若规定根结点的层数为 1 ，则深度为 h 的⼆叉树的最⼤结点数是 2 h − 1

        3）若规定根结点的层数为 1 ，具有 n 个结点的满⼆叉树的深度 ( log

              以2为底， n+1 为对数)

2.3 ⼆叉树存储结构

2.3.1 顺序结构

2.3.2 链式结构

3. 实现顺序结构⼆叉树

3.1 堆的概念与结构

堆具有以下性质

💡 ⼆叉树性质

• 对于具有 n 个结点的完全⼆叉树，如果按照从上⾄下从左⾄右的数组顺序对所有结点从

  0 开始编号，则对于序号为 i 的结点有：

1. 若 i>0 ， i 位置结点的双亲序号： (i-1)/2 ； i=0 ， i 为根结点编号，⽆双亲结点

2. 若 2i+1<n ，左孩⼦序号： 2i+1 ， 2i+1>=n 否则⽆左孩⼦

3. 若 2i+2<n ，右孩⼦序号： 2i+2 ， 2i+2>=n 否则⽆右孩⼦

3.2 堆的实现

void HPInit(HP* php) {assert(php);php->arr = NULL;php->size = php->capacity = 0;
}

插入数据

//交换
void Swap(int* x, int* y)
{int tmp = *x;*x = *y;*y= tmp;
}
//向上调整
void	AddjustUp(HPDataType* arr, int size)
{int parent = (size - 1) / 2;while (size>=0){if (arr[size] < arr[parent]){Swap(&arr[size], &arr[parent]);size = parent;parent = (size - 1) / 2;}else{break;}}
}
void HPPush(HP* php, HPDataType x)
{assert(php);if (php->capacity == php->size){int newcapacity = php->capacity == 0 ? 4 : 2 * php->capacity;HPDataType* tmp = (HP*)realloc(php->arr, newcapacity * sizeof(HPDataType));if (tmp == NULL){perror("realloc fail!");exit(1);}php->arr = tmp;php->capacity = newcapacity;}php->arr[php->size] = x;AddjustUp(php->arr, php->size);++php->size;
}

删除数据

void Swap(int* x, int* y)
{int tmp = *x;*x = *y;*y= tmp;
}
void AddjustDown(HPDataType* arr, int parent, int n)
{int child = parent * 2 + 1;while (child<n){if (child+1<n && arr[child] > arr[child + 1]){child++;}if (arr[child] < arr[parent]){Swap(&arr[child], &arr[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}
void HPPop(HP* php)
{assert(php && php->size);Swap(&php->arr[0], &php->arr[php->size - 1]);--php->size;AddjustDown(php->arr, 0, php->size);
}

判空

bool HPEmpty(HP* php)
{assert(php);return php->size == 0;
}

打印堆顶数据

HPDataType HPTop(HP* php)
{assert(php && php->size);return php->arr[0];
}

3.2.1 向上调整算法

 void AdjustUp(HPDataType* a, int child)
{int parent = (child - 1) / 2;while(child > 0){if (a[child] > a[parent]){Swap(&a[child], &a[parent]);child = parent;parent = (parent - 1) / 2;}else{break;}}
}
void HPPush(HP* php, HPDataType x)
{assert(php);if (php->size == php->capacity){size_t newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;HPDataType* tmp = realloc(php->a, sizeof(HPDataType) * newCapacity);if (tmp == NULL){perror("realloc fail");return;}php->a = tmp;php->capacity = newCapacity;}php->a[php->size] = x;php->size++;AdjustUp(php->a, php->size-1);
}

💡 向上调整算法建堆时间复杂度为： O ( n ∗ log 2 n )

💡 向下调整算法

        • 将堆顶元素与堆中最后⼀个元素进⾏交换

        • 删除堆中最后⼀个元素

        • 将堆顶元素向下调整到满⾜堆特性为⽌

💡 向下调整算法建堆时间复杂度为： O ( n )