堆和堆排序
原创
堆和堆排序
1.堆排序简介
堆排序是基于堆这种数据结构设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为O(nlogn)，是不稳定排序。
2.堆
2.1简介
首先介绍堆这种数据结构,对于堆的认识,只需要把握它的两个特点：
- 1.堆是一个完全二叉树,那么它就有完全二叉树的一些特性
- 2.堆的每个节点元素都有一定的规律,即每个节点都要大于它的左右孩子节点,对应于大顶堆;或者每个节点小于它的孩子节点,对应于小顶堆。
完全二叉树
1.上图是一个完全二叉树，也是一个大顶堆
完全二叉树:从根节点开始到这颗数最后一个节点，我们每一层从左到右去观察，中间若没有缺少节点，那么便是完全二叉树 3.完全二叉树的存储可以使用数组，如果我们对树中节点进行编号，从上到下，从左到右逐层编号，在将该编号作为数组索引下标存入数组。 4.完全二叉树规律，如图中完全二叉树，任意一个节点的左孩子节点为2*i,即拿编号乘以2得到左孩子下标，同理右孩子下标为2*i+1
2.2构建堆
构建思路： 首先堆是一个完全二叉树，我们在插入元素时，要保证插入后它还是一个完全二叉树，解决这一问题很简单，只需要在堆中已经有的元素后面插入进去即可。 然后便是保证每个节点大于它的孩子节点这一特性，我们只需要将刚刚插入的节点不断地和它的父节点比较，如果它小于父节点，那么运气很好，这个位置就是它该待的位置，不需要处理。如果该值大于它的父节点，则与父节点交换位置，也就是将它移到父节点的位置上，父节点跑到它的位置上，然后继续在新的位置上继续和它的父节点比较。
给定序列:1,5,4,10,6,9 逐个添加元素建立大顶堆为了处理方便，我们不使用下标为0的这一块数组区域
经过上述的流程，便建立一个堆了
2.3删除堆中元素
输出思路: 对于一个堆，我们可以将它看做超市里面水果塔，将水果不断堆叠向上，像一个金字塔一样，如果我们随心所欲的随意拿走任意一个，必然会导致这个水果塔崩塌，但是我们可以每次从最上面拿，这样就不会出错。 以此为例说明堆的删除流程
在这里插入图片描述
将10删除，此时就不在是一个堆了，我们该如何操作让它依然是一个堆？我们可以让最后一个元素移动到10所在位置，保证了整体还是一颗完全二叉树
以此规律不断进行下去，即可删除堆中所有元素
3.堆排序
观察堆，我们可以发现堆顶那个元素总是最大的或最小的，这取决于你构建的是大顶堆还是小顶堆。设想我们每次删除一个堆中元素，总是该堆中目前最大的一个，我们一直不断删除，根据删除的先后顺序，得到的便是一个有序序列了。 删除堆中一个元素，堆中的元素就少了一个，在我们代码实现的数组中，那块空间始终固定不变，在我们删除一个元素时，数组就空出一个空间，我们可以利用这块空间，存储被删除的元素，最后得到一个有序序列
代码
type Heap struct {
data [51]int
counter int
}
var heap Heap
func addElement(data int) {
heap.data[heap.counter+1] = data
heap.counter++
current, parent := heap.counter, heap.counter
for {
current = parent
parent = parent / 2
if parent <= 0 {
break
}
if heap.data[parent] > heap.data[current] {
heap.data[parent], heap.data[current] = heap.data[current], heap.data[parent]
} else {
break
}
}
}
func getHeapElement() (data int) {
if heap.counter <= 0 {
return -1
} else {
return heap.data[1]
}
}
func deleteElement() {
if heap.counter <= 0 {
return
}
index := 1
heap.data[index] = heap.data[heap.counter]
heap.counter--
for {
if 2*index > heap.counter {
break
}
if 2*index+1 > heap.counter {
if heap.data[index] > heap.data[2*index] {
heap.data[index], heap.data[2*index] = heap.data[2*index], heap.data[index]
index = index * 2
break
} else {
break
}
}
if heap.data[2*index] < heap.data[2*index+1] {
if heap.data[index] > heap.data[2*index] {
heap.data[index], heap.data[2*index] = heap.data[2*index], heap.data[index]index = index * 2
} else {
break
}
} else {
if heap.data[index] > heap.data[2*index+1] {
heap.data[index], heap.data[2*index+1] = heap.data[2*index+1], heap.data[index]index = 2*index + 1
} else {
break
}
}
}
}以上是关于堆以及堆排序的学习与认识，如有错误，欢迎指出。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
腾讯云开发者
