From the wiki
The maximum number of children each node can have depends on the type of heap, but in many types it is at most two, which is known as a binary heap.
I can't understand why in many types the node in heap at most has only two children? Why three children or four children and so on is not common? Thanks~
It's not true that most types of heap have at most two children per node, but it is true that the binary heap -- which does have at most two children per node -- is the most commonly implemented type. It's the most commonly implemented type because it is simple, cache-friendly, and memory-efficient.
The data structures used for binary heaps could be used with a different number of children per node. The common operations in an x-ary heap would still take O(log N) time, if we consider x to be constant. To decide on the best x, however, we have to let it vary, and in that case common operations take O(x * log N / log x) time.
To determine the most efficient number of children per node, we can choose x to minimize the factor x/log x.
If you plot that you can see that the best number of children per node is actually 3 (the minimum is at x=e, but we require an integer):
... but the difference between 2 and 3 is not significant, and the code is simpler using 2 children per node, so that is the common practice.
