堆排序-树

二叉树性质

数组存储的二叉树 对于一个节点下标i,其子节点的下标是 2i+1,2i+2,其父节点的下标是 （i-1)/2

堆： 完全二叉树或近似完全二叉树
大顶堆 父节点比子节点大 小顶堆 父节点比子节点小 兄弟节点对于大小和顺序没有要求。

遍历

先序遍历 先根，再左右 中序遍历 先左再根再右 后序遍历 先左再右再根 这里的先中后可以理解为父节点的输出位置

建堆

从下标(n-1)2开始往前逐个对下标所在节点建堆。 时间复杂度 NlogN

排序

将未排序的数组首尾对调，然后对堆顶建堆，重建后的堆顶即为最大值或最小值，与尾部对调，重复之前的操作。 时间复杂度 N*logN

	private void sortHeap(int[] a){
		//建堆  从最后一个叶子结点开始
		for (int i = (a.length-1-1)/2; i >=0 ; i--) {
			heapAdjust(a,i,a.length-1);
		}
		//排序 每次将堆顶的数放到未排序数组的末尾
		for (int i = a.length -1; i >=0 ; i--) {
			swap(a,0,i);
			heapAdjust(a,0,i-1);
		}
	}

	private void heapAdjust(int[]a,int l,int r){
		int temp = a[l];
		int parent = l;
		for(int child = l*2+1; child <r; child = child *2+1){
			if (a[child]<a[child +1]){
				child++;
			}
			if (temp<a[child]){
				a[parent] = a[child];
				parent = child;
			}else {
				break;
			}
		}
		a[parent] = temp;
	}

红黑树

前缀树 字典树

用于保存大量的字符串 可以利用字符串的公共前缀缩小查词的搜索范围，高效检索