如何实现最大堆

问题描述 投票：0回答：3

我有构建最大堆的代码，但它不断返回我给它的相同数组。我确信这是一个小错误，但我似乎无法弄清楚。如有任何帮助，我们将不胜感激。

可编译示例代码：

#include <iostream>
#include <cmath>

class Heaparr {
public:
    Heaparr();
    void insert(int da);
    int getLeft(int i) { return 2 * i; }
    int getRight(int i) { return (2 * i) + 1; }
    int getParent(int i) { return i / 2; }
    int getMax() { return maxHeap[0]; }
    void print();
    void reheap(int num);
    void makeArray();
    void Build_Max_Heap(int maxHeap[], int heap_size);
    void Max_Heapify(int heapArray[], int i, int heap_size);
    void heapSort(int heapArray[]);

private:
    int size;
    int* maxHeap;
    int index;
    int i;
};

Heaparr::Heaparr() {
    maxHeap = nullptr;
    size = 0;
}

void Heaparr::insert(int da) {
    size++;
    int* tmp = new int[size];

    for (int i = 0; i < size - 1; i++) {
        tmp[i] = maxHeap[i];
    }

    tmp[size - 1] = da;
    delete[] maxHeap;
    maxHeap = tmp;
}

void Heaparr::heapSort(int maxHeap[]) {
    int heap_size = size;
    int n = size;
    int temp;

    Build_Max_Heap(maxHeap, heap_size);

    for (int i = n - 1; i >= 1; i--) {
        temp = maxHeap[0];
        maxHeap[0] = maxHeap[i];
        maxHeap[i] = temp;

        heap_size = heap_size - 1;
        Max_Heapify(maxHeap, 0, heap_size);
    }

    for (int i = 0; i < 8; i++) {
        std::cout << maxHeap[i] << std::endl;
    }
}

void Heaparr::Build_Max_Heap(int maxHeap[], int heap_size) {
    int n = size;
    for (int i = floor((n - 1) / 2); i >= 0; i--) {
        Max_Heapify(maxHeap, i, heap_size);
    }
    return;
}

void Heaparr::Max_Heapify(int heapArray[], int i, int heap_size) {
    // int n = size;
    int largest = 0;
    int l = getLeft(i);
    int r = getRight(i);

    if ((l <= heap_size) && (heapArray[l] > heapArray[i])) {
        largest = l;
    } else {
        largest = i;
    }

    if ((r <= heap_size) && (heapArray[r] > heapArray[largest])) {
        largest = r;
    }

    int temp;
    if (largest != i) {
        temp = heapArray[i];
        heapArray[i] = heapArray[largest];
        heapArray[largest] = temp;

        Max_Heapify(heapArray, largest, heap_size);
    }
    return;
}

int main(int argc, char* argv[]) {
    int hArray[8] = {5, 99, 32, 4, 1, 12, 15, 8};
    Heaparr t;
    t.heapSort(hArray);
    for (auto v : hArray) {
        std::cout << v << ", ";
    }
    std::cout << std::endl;
}
c++ arrays heap
3个回答
1
投票

我对代码进行了一些修复（我尽量不对原始代码进行太多更改）：

  • getLeft
    、
    getRight
    和
    getParent
    公式是错误的（例如：当
    i == 0
    子级必须是1和2并且您的代码是0和1时）。返回类型也是错误的，应该是 
    int
    （数组索引）。
  • 您是否在所有方法中都收到
    int[]
    ，除了
    insert
    和
    member variable
    ，即
    double[]
    ，全部更改为
    int[]
    ，如果您需要全部更改回double
  • 使用 
    std::swap
    交换数组中的值。
  • 将数组的长度添加到heapSort（方法内部此信息丢失，需要通过参数传递）。

备注：

  • 我没有看到你在哪里使用了成员变量
    maxHeap
    ，因为除了
    getMax
    和
    insert
    之外的所有方法都使用参数传递的数组而不是成员变量（也许你应该在构造函数或
    heapSort
    方法中初始化） .
  • 尝试使用 
    std::vector
    代替 
    C Array

代码：

#include <iostream>
#include <cmath>

class Heaparr {
public:
    Heaparr();
    void insert(int da);
    int getLeft(int i) { return 2 * i + 1; }
    int getRight(int i) { return 2 * i + 2; }
    int getParent(int i) { return (i - 1) / 2; }
    int getMax() { return maxHeap[0]; }
    void print();
    void reheap(int num);
    void makeArray();
    void Build_Max_Heap(int heapArray[], int heap_size);
    void Max_Heapify(int heapArray[], int i, int heap_size);
    void heapSort(int heapArray[], int heap_size);

private:
    int size;
    int* maxHeap;
    int index;
    int i;
};

Heaparr::Heaparr() {
    maxHeap = nullptr;
    size = 0;
}

void Heaparr::insert(int da) {
    size++;
    int* tmp = new int[size];

    for (int i = 0; i < size - 1; i++) {
        tmp[i] = maxHeap[i];
    }

    tmp[size - 1] = da;
    delete[] maxHeap;
    maxHeap = tmp;
}

void Heaparr::heapSort(int heapArray[], int heap_size) {
    size = heap_size;
    int n = size;
    Build_Max_Heap(heapArray, heap_size);

    for (int i = n - 1; i >= 1; i--) {
        std::swap(heapArray[0], heapArray[i]);
        heap_size = heap_size - 1;
        Max_Heapify(heapArray, 0, heap_size);
    }
}

void Heaparr::Build_Max_Heap(int heapArray[], int heap_size) {
    int n = size;
    for (int i = floor((n - 1) / 2); i >= 0; i--) {
        Max_Heapify(heapArray, i, heap_size);
    }
    return;
}

void Heaparr::Max_Heapify(int heapArray[], int i, int heap_size) {
    // int n = size;
    int largest = 0;
    int l = getLeft(i);
    int r = getRight(i);

    if ((l < heap_size) && (heapArray[l] < heapArray[i])) {
        largest = l;
    } else {
        largest = i;
    }

    if ((r < heap_size) && (heapArray[r] < heapArray[largest])) {
        largest = r;
    }

    if (largest != i) {
        std::swap(heapArray[i], heapArray[largest]);
        Max_Heapify(heapArray, largest, heap_size);
    }
    return;
}

int main(int argc, char* argv[]) {
    int hArray[8] = {5, 99, 32, 4, 1, 12, 15, 8};

    Heaparr t;
    t.heapSort(hArray, sizeof(hArray)/sizeof(hArray[0]));
    for (auto v : hArray) {
        std::cout << v << ", ";
    }
    std::cout << std::endl;
    return 0;
}

输出： 

99, 32, 15, 12, 8, 5, 4, 1,

在 GCC 4.9.0 中使用 C++11 进行测试

0
投票

如果您愿意考虑替代实现，那么这里有一个：

#define MIN_TYPE  0
#define MAX_TYPE ~0

template<int TYPE,typename ITEM>
class Heap
{
public:
    Heap(int iMaxNumOfItems);
    virtual ~Heap();
public:
    bool AddItem(ITEM*  pItem);
    bool GetBest(ITEM** pItem);
protected:
    int  BestOfTwo(int i,int j);
    void SwapItems(int i,int j);
protected:
    ITEM** m_aItems;
    int    m_iMaxNumOfItems;
    int    m_iCurrNumOfItems;
};

template<int TYPE,typename ITEM>
Heap<TYPE,ITEM>::Heap(int iMaxNumOfItems)
{
    m_iCurrNumOfItems = 0;
    m_iMaxNumOfItems = iMaxNumOfItems;
    m_aItems = new ITEM*[m_iMaxNumOfItems];
    if (!m_aItems)
        throw "Insufficient Memory";
}

template<int TYPE,typename ITEM>
Heap<TYPE,ITEM>::~Heap()
{
    delete[] m_aItems;
}

template<int TYPE,typename ITEM>
bool Heap<TYPE,ITEM>::AddItem(ITEM* pItem)
{
    if (m_iCurrNumOfItems == m_iMaxNumOfItems)
        return false;

    m_aItems[m_iCurrNumOfItems] = pItem;

    for (int i=m_iCurrNumOfItems,j=(i+1)/2-1; j>=0; i=j,j=(i+1)/2-1)
    {
        if (BestOfTwo(i,j) == i)
            SwapItems(i,j);
        else
            break;
    }

    m_iCurrNumOfItems++;

    return true;
}

template<int TYPE,typename ITEM>
bool Heap<TYPE,ITEM>::GetBest(ITEM** pItem)
{
    if (m_iCurrNumOfItems == 0)
        return false;

    m_iCurrNumOfItems--;

    *pItem = m_aItems[0];
    m_aItems[0] = m_aItems[m_iCurrNumOfItems];

    for (int i=0,j=(i+1)*2-1; j<m_iCurrNumOfItems; i=j,j=(i+1)*2-1)
    {
        if (j+1 < m_iCurrNumOfItems)
            j = BestOfTwo(j,j+1);
        if (BestOfTwo(i,j) == j)
            SwapItems(i,j);
        else
            break;
    }

    return true;
}

template<int TYPE,typename ITEM>
int Heap<TYPE,ITEM>::BestOfTwo(int i,int j)
{
    switch (TYPE)
    {
        case MIN_TYPE: return *m_aItems[i]<*m_aItems[j]? i:j;
        case MAX_TYPE: return *m_aItems[i]>*m_aItems[j]? i:j;
    }
    throw "Illegal Type";
}

template<int TYPE,typename ITEM>
void Heap<TYPE,ITEM>::SwapItems(int i,int j)
{
    ITEM* pItem = m_aItems[i];
    m_aItems[i] = m_aItems[j];
    m_aItems[j] = pItem;
}

这是一个用法示例：

typedef int ITEM;
#define SIZE 1000
#define RANGE 100

void test()
{
    ITEM* pItem;
    ITEM aArray[SIZE];
    Heap<MIN_TYPE,ITEM> cHeap(SIZE);

    srand((unsigned int)time(NULL));

    for (int i=0; i<SIZE; i++)
    {
        aArray[i] = rand()%RANGE;
        cHeap.AddItem(aArray+i);
    }

    for (int i=0; i<SIZE; i++)
    {
        cHeap.GetBest(&pItem);
        printf("%d\n",*pItem);
    }
}

描述：

  • 此类最多可存储 

    N
    类型为 
    T

    • 的项目

  • 它允许添加项目或提取最佳项目

  • 支持的操作在

    O(log(n))
    完成，其中
    n
    是当前的项目数

备注：

  • T
    在声明时确定，
    N
    在初始化时确定

  • “最佳”的含义，无论是最小还是最大，都是在声明时确定的

  • 为了支持

    Heap<MIN,T>
    和
    Heap<MAX,T>
    ，以下选项之一必须可行：

    1. bool operator<(T,T)
      和 
      bool operator>(T,T)

    2. bool T::operator<(T)
      和 
      bool T::operator>(T)

    3. T::operator P()
      ，其中 
      P
      是一种类型，对于该类型，上述选项之一是可行的

0
投票

import java.util.ArrayList;
import java.util.List;

public class Heap {
    private List<Integer> heap;

    public Heap() {
        this.heap = new ArrayList<>();
    }

    public List<Integer> getGeap() {
        return new ArrayList<>(this.heap);
    }

    private int leftChild(int index) {
        return index * 2 + 1;
    }

    private int rightChild(int index) {
        return index * 2 + 2;
    }

    private int parent(int index) {
        return (index - 1) / 2;
    }

    private void swap(int index1, int index2) {
        int temp = heap.get(index1);
        heap.set(index1, heap.get(index2));
        heap.set(index2, temp);
    }

    public void insert(int value) {
        heap.add(value);
        int current = heap.size() - 1;

        while (current > 0 && heap.get(current) > heap.get(parent(current))) {
            swap(current, parent(current));
            current = parent(current);
        }
    }

    public static void main(String[] args) {
        int[] A = { 99, 61, 58, 18, 27, 55, 72 };
        Heap hp = new Heap();
        for (int i = 0; i < A.length; i++) {
            hp.insert(A[i]);
        }
        // PriorityQueue<Integer> q = new PriorityQueue<>();

        // System.out.println(hp.leftChild(2));
        // System.out.println(hp.rightChild(0));
        System.out.println(hp.getGeap());
    }
}
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.