标签为 [堆排序] 的文章

算法初级——堆排序

堆 堆分为大根堆和小根堆,大根堆就是所有的根节点都比他的子节点都要大,小根堆同理。 我们进行堆排序的时候,其实并不是真的要用到二叉树(完全二叉树),而只是借用这个形式来理解排序的过程,可以将一个数组想象成一棵树。例如i节点的父节点就是(i-1)/2,i节点的左子节点就是i*2+1,右子节点就是i*2+2。 heapInsert:将数组的0到1位置的数变成一个大根堆,然后加入2位置的数,整体是一个大根堆,方法就是刚进来的i位置的数与他的父节点比较,如果大于父节点就交换,然后i位置变成了他的父节点的位置,然后再比较i位置与他的 ......