大師兄的數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)筆記(六）:樹(shù)的應(yīng)用
大師兄的數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)筆記(八）: 哈夫曼樹(shù)與哈夫曼編碼

一、什么是堆(Heap)

• 可以看作是一個(gè)數(shù)組表示的完全二叉樹(shù)。
• 堆總是滿足下列性質(zhì)：

1) 堆中某個(gè)節(jié)點(diǎn)的值總是不大于或不小于其父節(jié)點(diǎn)的值。
2) 堆總是一棵完全二叉樹(shù)。

• 將根節(jié)點(diǎn)最大的堆叫做最大堆(MaxHeap)。

  
  

• 根節(jié)點(diǎn)最小的堆叫做最小堆(MinHeap)。

  
  

二、堆的抽象數(shù)據(jù)類型描述

• 操作集:。
• 主要操作有:

三、堆的實(shí)現(xiàn)

#ifndef MAXHEAP
#define MAXHEAP
#include<vector>
using namespace std;

template<class T>
class MyMaxHeap
{
public:
    MyMaxHeap(T data[], int len);   //構(gòu)造函數(shù)
    MyMaxHeap(int capacity);        //構(gòu)造一個(gè)空堆
    ~MyMaxHeap(){};                 //析構(gòu)函數(shù)
    bool IsFull();                  //判斷最大堆H是否已滿。
    void Insert(T item);        //將元素item插入最大堆H。
    bool IsEmpty();                 //判斷最大堆H是否為空
    T DeleteMax();          //返回最大元素

private:
    vector<T>_vecdata;
    int _size;                      //元素?cái)?shù)量
    int _capacity;                  //堆的大小
    void _swap(int i, int j );      //元素交換
    void _sink(int index);          //元素下沉
    void _floating(int index);      //元素上浮
};

#endif

#include <iostream>
#include "heap.h"
using namespace std;
//構(gòu)造函數(shù)
template <class T>
MyMaxHeap<T>::MyMaxHeap(T data[], int len) :_size(0), _capacity(len)
{
    _vecdata.resize(_capacity);
    for (int i = 0; i < len; i++)
    {
        if (IsFull())
        {
            cout << "MaxHeap is full!" << endl;
        }
        else
        {
            _vecdata[_size] = data[i];
            ++_size;
            _floating(_size);
        }
    }
}

template <class T>
//構(gòu)造一個(gè)空堆
MyMaxHeap<T>::MyMaxHeap(int capacity) :_size(0), _capacity(capacity)
{
    _vecdata.resize(_capacity);
}

template <class T>
//判斷最大堆H是否已滿
bool MyMaxHeap<T>::IsFull()
{
    if (_capacity == _size)
        return true;
    return false;
}

template <class T>
//將元素item插入最大堆H
void MyMaxHeap<T>::Insert(T item)
{
    if (IsFull())
    {
        cout << "the MaxHeap is full!!" << endl;
        return;
    }
   
    _vecdata[_size] = item;
    ++_size;
    _floating(_size);
}

template <class T>
//判斷最大堆H是否為空
bool MyMaxHeap<T>::IsEmpty()
{
    return _size == 0;
}

template <class T>
//返回最大元素
T MyMaxHeap<T>::DeleteMax()
{
    if (IsEmpty())
    {
        cout << "the MaxHeap is empty!" << endl;
        return nullptr;
    };
    T max_data = _vecdata[0];
    _vecdata[0] = _vecdata[_size - 1];
    --_size;
    _sink(_size + 1);
    return max_data;
}

template <class T>
//元素交換
void MyMaxHeap<T>::_swap(int i, int j)
{
    T temp = _vecdata[i];
    _vecdata[i] = _vecdata[j];
    _vecdata[j] = temp;
    return;
}

template <class T>
//元素下沉
void MyMaxHeap<T>::_sink(int index)
{
    int i = index;
    while (i * 2 <= _size)
    {
        //對(duì)比左節(jié)點(diǎn)
        if (_vecdata[i - 1] < _vecdata[i * 2 - 1])
        {
            _swap(i - 1, i * 2 - 1);
            if (i * 2 + 1 <= _size && _vecdata[i - 1] < _vecdata[i * 2])
                _swap(i - 1, i * 2);
            i = i * 2;
        }
        //對(duì)比右節(jié)點(diǎn)
        else if (i * 2 + 1 <= _size && _vecdata[i - 1] < _vecdata[i * 2])
        {
            _swap(i - 1, i * 2);
            i = i * 2 + 1;
        }
        else
            break;
    }
}

template <class T>
//元素上浮
void MyMaxHeap<T>::_floating(int index)
{
    if (_size == 1)
        return;
    for (int i = index; i > 0; i *= 0.5)
    {
        if (_vecdata[i - 1] > _vecdata[i * 0.5 - 1])
            _swap(i - 1, i * 0.5 - 1);
        else
            break;
    }
}