数据结构:堆

2018-09-04

数据结构-堆

堆是优先级队列的另一种实现结构,堆是一种数（插入和删除时间复杂度O(logN)）
使用场景：速度非常重要，且有很多插入操作时，可以选择堆实现优先级队列

堆特点

完全二叉树
常常用一个数组实现
堆中的每一个节点都满足堆的条件，每一个关键字都大于或等于这个节点的子节点的关键字

用数组表示一颗树的要点，若数组中节点的索引为x则

父节点=(x-1)/2
左子节点=2x+1
右子节点=2x+2

前段时间自学了python，这次用python实现堆排序

Node.py

1
2
3

class Node:
    def __init__(self,key):
        self._key=key

堆结构Heap.py

import Node
class Heap:
	#初始化
    def __init__(self,max):
        self._currentSize=0
        self._maxSize=max
        self._heapArray=[0]*max
	
	#插入新节点方法省略
	def insert(self,key):
	#删除节点方法省略
	def remove(self):
	#改变节点值方法省略
	def change(self,index,newValue);

1.插入方法

"heap-insert"

步骤：

最后一个位置添加新节点
向上跟父节点筛选比较大小，直到它在一个大于它的节点之下，小于它的节点之上

def trickleUp(index):
	
	parentIndex=(index-1)/2		#获取新节点的父节点
	
	bottom=self._heapArray[index]	#获取刚加入的新节点
	#只要没有到根节点新节点比父节点大就交换位置
	while index>0 and self._heapArray[parentIndex]._key<bottom._key:
		self._heapArray[index]=self._heapArray[parentIndex]
		index=parentIndex
		parentIndex=(parentIndex-1)/2	#获取新的父节点位置
	self._heapArray[index] = bottom	#把新节点交换到指定位置

def insert(self,key):
	if self._currentSize>=self._maxSize:
		return False
	#初始化节点，设定到最后一个数组索引下
	newNode=Node.Node(key)
	self._heapArray[self._currentSize]=newNode
	
	#向上和父节点比较大小并交换位置
	self._trickleUp(self._currentSize)
	
	self._currentSize += 1	#加一
	return True

2.移除方法

"heap-delete"

步骤：

移走根
把最后一个节点移动到根的位置
一直向下筛选这个节点，直到他在一个大于它的节点之下，小于它的节点之上
向下筛选的算法要检查哪一个子节点更大，然后目标节点和较大的子节点交换，否则违背了堆的条件（父节点大于子节点）

def _trickleDown(self,index):
	top=self._heapArray[index]		#保存最新节点
	largerIndex=0		
	while index<self._currentSize/2:	#循环直到有子节点
		leftChild=index*2+1				#计算左子节点索引位置
		rightChild=leftChild+1
		if self._heapArray[leftChild]._key<self._heapArray[rightChild]._key:	#比较左右节点哪个更大
			largerIndex=rightChild
		else:
			largerIndex=leftChild
			
		if top._key>=self._heapArray[largerIndex]._key:		#找到最终位置，新节点大于等于最大子节点就退出
			break
		self._heapArray[index]=self._heapArray[largerIndex]	#交换位置
		index=largerIndex
	self._heapArray[index]=top			#新节点设值到该index

def remove(self):
	root=self._heapArray[0]		#获得根节点
	self._currentSize-=1;
	self._heapArray[0]=self._heapArray[self._currentSize]	#最后一个位置索引交换到根节点位置
	self._trickleDown(0)
	return root

3.改变节点值

"heap-change"

改变一个已存在节点的优先级，

获取旧值
索引位置被替换为新值
比较旧值和新值如果新值大于旧值就向上筛选，否则向下筛选

def change(self,index,newValue):
	if index<0 or index>self._currentSize:
		return False
	
	oldValue=self._heapArray[index]._key	#获取要被替换的旧值
	
	self._heapArray[index]._key=newValue	#设定被替换的索引值为新值
	
	if oldValue<newValue:	#如果新值大于旧值就向上替换
		self._trickleUp(index)
	else:
		self._trickleDown(index)	#向下替换
	return True

注:该内容为Java数据结构和算法读后学习感悟