即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

《数据结构实战》———————— 一个二叉堆的实现

编程语言 li2818 14℃ 0评论

该代码是一个二叉堆的实现,堆排序。

#ifndef __CBINARYHEAP__H
#define __CBINARYHEAP__H
#include 
#include 

// 小根堆的实现
// 没有值的节点填充为-9999

class CBinaryHeap
{
public:
 CBinaryHeap(int nSize); // 初始大小
 ~CBinaryHeap();

public:
 bool InsertNode(int nValue); // 插入数据
 bool DeleteMin(); // 删除最小值
 int  GetMin(); // 获取最小值
private:
 void Resize();
 void PullDown(int nIndex, int nLast); // 找到左右节点中更小的 并进行填充
private:
 int m_nSize;
 int m_nCurrentPos;
 std::vector m_vectBinaryHeap;
};

#endif


#include "BinaryHeap.h"



CBinaryHeap::CBinaryHeap(int nSize) : m_nSize(nSize)
{
 m_vectBinaryHeap.resize(m_nSize);
 for (int i = 0; i < m_nSize; i++)
 {
  m_vectBinaryHeap[i] = -9999;
 }
 m_nCurrentPos = 0;
}


CBinaryHeap::~CBinaryHeap()
{
}

bool CBinaryHeap::InsertNode(int nValue)
{
 if (m_nCurrentPos == m_nSize) // 扩展
  Resize(); // 扩展大小
 m_nCurrentPos++; // 下一个节点肯定是空的
 int nHole = m_nCurrentPos;
 for (; nHole > 1 && nValue < m_vectBinaryHeap[nHole / 2]; nHole /= 2) // 小于
  m_vectBinaryHeap[nHole] = m_vectBinaryHeap[nHole / 2]; // 将父节点填充到该节点
 m_vectBinaryHeap[nHole] = nValue;
 return true;
}

void CBinaryHeap::Resize()
{
 std::vector vectTemp;
 vectTemp.swap(m_vectBinaryHeap);
 m_vectBinaryHeap.resize(m_nSize * 2);
 m_vectBinaryHeap.swap(vectTemp);
 for (int i = m_nCurrentPos; i++; i < m_nSize * 2)
  m_vectBinaryHeap[i] = -9999;
 m_nSize *= 2;
}

int CBinaryHeap::GetMin()
{
 return m_vectBinaryHeap[1]; // 1处的元素是最小的
}

bool CBinaryHeap::DeleteMin() // 删除最小值
{
 int nLast = m_vectBinaryHeap[m_nCurrentPos--]; // 先找出最后一个元素 再进行填充
 PullDown(1, nLast);
 return true;
}

void CBinaryHeap::PullDown(int nIndex, int nLast)
{
 if (2 * nIndex > m_nSize || 2 * nIndex + 1 > m_nSize) // 没有左右节点
 {
  m_vectBinaryHeap[nIndex] = nLast;
  return;
 }
 if (m_vectBinaryHeap[2 * nIndex] == -9999 && m_vectBinaryHeap[2 * nIndex + 1] == -9999) // 没有左右节点
 {
  m_vectBinaryHeap[nIndex] = nLast;
  return;
 }
 if (m_vectBinaryHeap[2 * nIndex + 1] == -9999) // 没有右节点
 {
  m_vectBinaryHeap[nIndex] = m_vectBinaryHeap[2 * nIndex];
  m_vectBinaryHeap[2 * nIndex] = nLast;
  return;
 }
 m_vectBinaryHeap[nIndex] = (m_vectBinaryHeap[2 * nIndex] < m_vectBinaryHeap[2 * nIndex + 1]) ? m_vectBinaryHeap[2 * nIndex] : m_vectBinaryHeap[2 * nIndex + 1];
 bool bLeft = (m_vectBinaryHeap[2 * nIndex] < m_vectBinaryHeap[2 * nIndex + 1]) ? true : false;
 PullDown(bLeft ? 2 * nIndex : 2 * nIndex + 1, nLast);
}


#include "BinaryHeap.h"

int main()
{
 CBinaryHeap binaryHeap(100);
 binaryHeap.InsertNode(31);
 binaryHeap.InsertNode(13);
 binaryHeap.InsertNode(16);
 binaryHeap.InsertNode(32);
 binaryHeap.InsertNode(68);
 binaryHeap.InsertNode(19);
 binaryHeap.InsertNode(65);
 binaryHeap.InsertNode(26);
 binaryHeap.InsertNode(21);
 binaryHeap.InsertNode(24);

 binaryHeap.DeleteMin();
 return 0;
}





转载请注明:CodingBlog » 《数据结构实战》———————— 一个二叉堆的实现

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情