在C++中，“堆”一词并不是指堆数据结构。在这里，“堆”指的是存储全局变量和静态变量的堆内存。另外，当我们动态分配内存时，它是在堆内存中分配的。

我的问题是，术语“堆”背后的数据结构是什么？

C++ heap organisation - which data structure?

C++的堆组织 - 使用哪种数据结构？

堆有两个主要含义，分别对应两种不同的概念：

1. 用于组织数据的数据结构，即树。

2. 可用内存的池。它通过分配/释放可用内存块来管理内存。

关于堆在内存管理中的介绍：

堆是另一个动态内存区域，由malloc/free及其变体分配/释放...

在C++中，堆是一种用于动态分配内存的重要数据结构。在程序运行时，堆可以用来存储动态分配的对象或数据。

堆的出现是因为在程序运行时，无法事先确定需要分配多少内存空间。因此，需要一种能够动态分配和管理内存的方法。而堆就是为此而设计的。它可以根据需要分配和释放内存块，以便在程序运行过程中动态地管理内存。

堆使用的数据结构通常是一种树的结构。这种树结构可以是二叉树、红黑树或其他类型的树，具体取决于编程语言和实现。

对于C++来说，堆是通过调用malloc、free和new、delete等函数来分配和释放内存的。这些函数会在堆中分配一块内存，并返回指向该内存块的指针。然后，程序可以使用该指针来访问和操作分配的内存。

使用堆的好处是可以在程序运行时动态地分配和释放内存。这样，程序就可以根据实际需求来管理内存，提高内存利用率。

需要注意的是，使用堆时需要注意内存泄漏的问题。如果分配了内存但没有释放，就会导致内存泄漏。因此，在使用堆时，需要确保及时释放不再使用的内存块，以避免内存泄漏的问题。

总结起来，堆是一种用于动态分配和管理内存的重要数据结构，它可以根据程序的实际需求来分配和释放内存。通过使用堆，可以提高内存利用率，并避免内存泄漏的问题。

C++堆组织-哪种数据结构更适合？

C++中的自由存储区域（free store）通常实现为一个链接的空闲内存块链表（即当前未使用的块）。堆管理器通常会从操作系统分配大块内存（例如每次1MB），然后将这些块分割成适用于代码的片段，以供new等操作使用。当使用delete时，不再使用的内存块将被添加到该链接列表中作为一个节点。

对于如何使用这些空闲块，有各种策略。其中三种常见的策略是最佳适应（best fit）、最差适应（worst fit）和首次适应（first fit）。

在最佳适应策略中，尝试找到一个与所需分配的大小最接近的空闲块。如果它比所需大小（通常在分配大小四舍五入后）更大，那么将其分割成两部分：一部分用于分配，另一部分（更小）作为新的空闲块放回链表中以满足其他分配请求。虽然这似乎是一个好的策略，但通常会出现问题。问题在于当你找到最接近的空闲块时，剩下的块通常太小而无法派上用场。经过一段时间后，你会得到大量的微小的自由空间块，这些块对于实现任何功能都没有什么用处。

最差适应策略则通过找到最大的空闲块来解决这个问题。当这个块被分割时，剩下的部分将尽可能大，最大化其对于其他分配的可用性。

首次适应策略只是遍历空闲块链表，并使用第一个足够大的块来满足需求。

相当多的情况下，管理器还会遍历空闲块链表的代码，以查找相邻的空闲块。如果找到了相邻的空闲块，它会将这两个小块合并为一个较大的块。有时，这是在free/delete块时立即执行的。更常见的是懒惰地执行，以避免在使用大量相同大小的块时重复执行合并和分割操作（这是相当常见的）。

当处理大量相同大小的项（尤其是小项）时，另一种常见的方法是使用一个块数组，其中包含一个位集来指示哪些块是空闲的或正在使用中。在这种情况下，通常会跟踪一个索引，该索引指向上一个空闲块的位集中的位置。当需要一个块时，只需从上一个索引开始向前搜索，直到找到位集中下一个空闲块。

以上是关于C++堆组织中数据结构选择的讨论。不同的策略适用于不同的场景，选择适当的策略可以优化内存管理和程序性能。