首页 > 代码库 > 堆 的取最值删除操作和插入操作
堆 的取最值删除操作和插入操作
堆的删除
按定义,堆中每次都只能删除第0个数据。为了便于重建堆,实际的操作是将最后一个数据的值赋给根结点,然后再从根结点开始进行一次从上向下的调整。调整时先在左右儿子结点中找最小的,如果父结点比这个最小的子结点还小说明不需要调整了,反之将父结点和它交换后再考虑后面的结点。相当于从根结点将一个数据的“下沉”过程。
堆的插入
每次插入都是将新数据放在数组最后。可以发现从这个新数据的父结点到根结点必然为一个有序的数列,现在的任务是将这个新数据插入到这个有序数据中——这就类似于直接插入排序中将一个数据并入到有序区间中。
代码:
#include <iostream> #include <algorithm> using namespace::std; //对排序实现类的定义 class HeapSort { public: HeapSort(int *pArray = NULL, int nArraySize = 0); ~HeapSort(); public: int *m_pA; int m_nHeapSize; public: void Sort(); int PopMaxHeap(); void InsertMaxHeap(int a); private: int LeftChild(int node); int RightChild(int node); int Parent(int node); void MaxHeapify(int nIndex); void BuildMaxHeap(); }; //对排序类成员函数的实现 HeapSort::HeapSort( int *pArray, int nArraySize ) { m_pA = pArray; m_nHeapSize = nArraySize; } HeapSort::~HeapSort() { } int HeapSort::Parent(int node) { return (node-1)/2 ; } int HeapSort::LeftChild(int node) { return 2*node + 1; } int HeapSort::RightChild(int node) { return 2*node + 2; } void HeapSort::MaxHeapify(int nIndex) { int nLeft = LeftChild(nIndex); int nRight = RightChild(nIndex); int nLargest = nIndex; if( (nLeft < m_nHeapSize) && (m_pA[nLeft] > m_pA[nIndex]) ) nLargest = nLeft; if( (nRight < m_nHeapSize) && (m_pA[nRight] > m_pA[nLargest]) ) nLargest = nRight; if ( nLargest != nIndex ) { swap<int>(m_pA[nIndex], m_pA[nLargest]); MaxHeapify(nLargest); } } void HeapSort::BuildMaxHeap() { if( m_pA == NULL ) return; for( int i = (m_nHeapSize - 1)/2; i >= 0; i-- ) { MaxHeapify(i); } } void HeapSort::Sort() { if( m_pA == NULL ) return; if( m_nHeapSize == 0 ) return; BuildMaxHeap(); for( int i = m_nHeapSize - 1; i > 0; i-- ) { swap<int>(m_pA[i], m_pA[0]); m_nHeapSize -= 1; MaxHeapify(0); } } int HeapSort::PopMaxHeap() { if( m_pA == NULL ) return -1; if( m_nHeapSize == 0 ) return -1; BuildMaxHeap(); int a= m_pA[0]; m_pA[0]=m_pA[m_nHeapSize-1]; m_nHeapSize -= 1; MaxHeapify(0); return a; } void HeapSort::InsertMaxHeap(int a) { /* if( m_pA == NULL ) return; if( m_nHeapSize == 0 ) return; */ m_nHeapSize += 1; m_pA[m_nHeapSize-1]=a; int index=m_nHeapSize-1; while(index>0) { if(m_pA[index]>m_pA[Parent(index)]) swap(m_pA[index], m_pA[Parent(index)]); index=Parent(index); } } int main() { //int A[14] = { 27,17,3,16,13,10,1,5,7,12,4,8,9,0 }; int A[10] = {4, 1, 3, 2, 16, 9, 10, 14, 8, 7}; cout<<"heapsort before:"; for(int i=0;i<10;++i) cout<<A[i]<<" "; cout<<endl; HeapSort mySort(A,10); /* mySort.Sort(); cout<<"heapsort after:"; for( int i = 0; i < 10; i++ ) cout << A[i] << " "; cout << endl; */ int a = mySort.PopMaxHeap(); cout<<"pop: "<<a<<endl; for(int i=0;i<10-1;++i) cout<<A[i]<<" "; cout<<endl; mySort.InsertMaxHeap(11); for(int i=0;i<10;++i) cout<<A[i]<<" "; cout<<endl; return 0; }
结果:
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。